by BehindJava

Write a program to find Duplicate character in a String Java

Home » java » Write a program to find Duplicate character in a String Java

In this tutorial we are going to learn about writing a program to find the duplicate characters in a String in 3 different ways.

Using for loops

  • Worst time complexity - Time Complexity: O(n2), where n = length of the string passed.

Using arrays of 256 size

  • Time Complexity: O(n), where n = length of the string passed.
  • Space Complexity: O(NOOFCHARS)

Using Map

  • Time Complexity: O(N log N), where N = length of the string passed and it generally takes logN time for an element insertion in a map.
  • Space Complexity: O(K), where K = size of the map (0=K=inputstringlength).

Using For Loops, Arrays, Map

import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;

public class DuplicateChar {

	public static void main(String args[]) {

		System.out.println(findDuplicatesUsingFor("geeks for monkeys")); // Time complexity = O(N2)

		System.out.println(findDuplicatesUsingArrays("geeks for monkeys")); // Time complexity = O(N) , Space complexity =
																		// O(256)
		System.out.println(findDuplicatesUsingMaps("geeks for monkeys")); // Time complexity = O(NLogn),
	}

	private static Set<Character> findDuplicatesUsingMaps(String name) {

		Set<Character> duplicates = new LinkedHashSet<>();
		HashMap<Character, Integer> countMap = new HashMap<Character, Integer>();
		for (int i = 0; i < name.length(); i++) { // O(n)
			if (countMap.containsKey(name.charAt(i))) {
				countMap.put(name.charAt(i), countMap.get(name.charAt(i)) + 1); // O(logn)
			} else {
				countMap.put(name.charAt(i), 1); 
			}
		}
		for (Map.Entry<Character, Integer> entry : countMap.entrySet()) {
			if (entry.getValue() > 1)
				duplicates.add(entry.getKey());
		}
		return duplicates;
	}

	private static Set<Character> findDuplicatesUsingArrays(String name) {
		Set<Character> duplicates = new LinkedHashSet<>();
		int[] arrayForChar = new int[256];

		for (int i = 0; i < name.length(); i++) // O(n)
			arrayForChar[name.charAt(i)] = arrayForChar[name.charAt(i)] + 1;

		for (int i = 0; i < 256; i++) { // O(n)
			if (arrayForChar[i] > 1)
				duplicates.add((char) i);
		}

		// O(2N) ~~ O(N)
		return duplicates;
	}

	private static Set<Character> findDuplicatesUsingFor(String name) {
		Set<Character> duplicates = new LinkedHashSet<>();
		for (int i = 0; i < name.length(); i++) { // O(n)
			for (int j = i + 1; j < name.length(); j++) { // O(n2)
				if (name.charAt(i) == name.charAt(j)) {
					duplicates.add(name.charAt(j));
				}
			}
		}
		return duplicates;
	}
}