by BehindJava
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("donkeys for monkeys")); // Time complexity = O(N2)
System.out.println(findDuplicatesUsingArrays("donkeys for monkeys")); // Time complexity = O(N) , Space complexity =
// O(256)
System.out.println(findDuplicatesUsingMaps("donkeys 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;
}
}Output:
[o, n, k, e, y, s, ]
[ , e, k, n, o, s, y]
[ , s, e, y, k, n, o]Share:
