Learn to write a simple Java program that finds the duplicate characters in a String. This can be a possible Java interview question while the interviewer may evaluate our coding skills.
We can use the given code to find repeated characters or modify the code to find non-repeated characters in the string.
1. Using Plain Java
Let us start with writing the program logic ourselves. In this solution, we are creating Map where each unique character in the string is the Map key, and the number of occurrences of the character is stored as the value.
1.1. Algorithm
- Split the string into a character array.
- Iterate over the character array.
- For each iteration, use the character as the Map key, and check if the same character is present in the map, already.
- If the map key does not exist, the character has been encountered for the first time. Store it in the map with a count value of 1.
- If the map key exists, increment the associated counter.
- Repeat until all characters in the array have been iterated.
- Check map. Duplicate characters have the count of more than 1.
- Distinct characters will have the count as 1.
1.2. Java Program
public static Map<Character, Integer> getCharBag(String input) {
Map<Character, Integer> map = new HashMap<>();
if(input == null || input.length() == 0)
return map;
for (char c : input.toCharArray()) {
if (map.containsKey(c)) {
int counter = map.get(c);
map.put(c, ++counter);
} else {
map.put(c, 1);
}
}
return map;
}
Now we can use the above Map to know the occurrences of each char and decide which chars are duplicates or unique.
//duplicate chars
List duplicateChars = bag.keySet()
.stream()
.filter(k -> bag.get(k) > 1)
.collect(Collectors.toList());
System.out.println(duplicateChars); //[a, o]
We can also find the duplicate characters and their count of occurrences in this string.
Map<Character, Integer> duplicateCharsWithCount = bag.entrySet()
.stream()
.filter(e -> bag.get(e.getKey()) > 1)
.collect(Collectors.toMap(p -> p.getKey(), p -> p.getValue()));
System.out.println(duplicateCharsWithCount); //{a=2, o=3}
Similarly, we can get all the unique characters by comparing the count to 1.
//unique chars
List duplicateChars = bag.keySet()
.stream()
.filter(k -> bag.get(k) == 1)
.collect(Collectors.toList());
System.out.println(duplicateChars); //[t, d, v, w, h, i, j, n]
2. Using Google Guava
The approach for finding duplicate characters remains the same, as discussed in the previous section. We will only replace the HashMap class with Multiset class from the Google Guava library.
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>31.1-jre</version>
</dependency>
We need to add all the characters to the Multiset one by one. The Multiset class allows the storage of multiple occurrences of the same element by tracking the count of each unique element it contains.
Multiset multiset = HashMultiset.create();
for (char c : input.toCharArray()) {
multiset.add(c);
}
From this point, we can use the Multiset to find distinct and unique characters using the similar logic in the previous section.
Map<Character, Integer> duplicateCharsWithCount = (Map<Character, Integer>) multiset.elementSet()
.stream()
.filter(k -> multiset.count(k) > 1)
.collect(Collectors.toMap(p -> p, p -> multiset.count(p)));
System.out.println(duplicateCharsWithCount); //{a=2, o=3}
We learned how we could use a map to find repeated characters in a string, also check non-repeated characters as well.
Happy Learning !!
Leave a Reply