Given an input string, Write a java code to find duplicate characters in a String.
For example :
Example 1:
Input : “Java”
Output : a
The character a appears more than once in a string.
Example 2:
Input : “programming”
Output : m,g,r
These three characters (m, g, r) appears more than once in a string.
In this tutorial, I am going to explain multiple approaches to solve this problem..
Find Duplicate Characters in a String using HashMap
In this example, I am using HashMap to print duplicate characters in a string.The time complexity of get and put operation in HashMap is O(1). That’s the reason we are using this data structure.
In HashMap, we store key and value pairs. So, in our case key is the character and value is it’s count. Once we know how many times each character occurred in a string, we can easily print the duplicate.
Any character which appears more than once in a string is a duplicate character.
The time complexity of this approach is O(1) and it’s space complexity is also O(1).
Find duplicate characters in a string video tutorial
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
//Find duplicate characters in a string using HashMap public class DuplicateCharacter { public static void printDuplicate(String str) { //Declare a map Map<Character, Integer> charMapCount = new HashMap<>(); /* Traverse a string and create a map of character and it's count */ for (int i = 0; i < str.length(); i++) { Character ch = str.charAt(i); //If key is already present in map if (charMapCount.containsKey(ch)) { charMapCount.put(ch, charMapCount.get(ch) + 1); } else { charMapCount.put(ch, 1); } } /* Traverse a map and print character whose count is greater than 1 */ charMapCount.forEach((k, v) -> { if(v > 1) { System.out.println(k); } }); } public static void main(String[] args) { String str = "java"; printDuplicate(str); } } |
Java program to reverse a string using stack
Find Duplicate Characters in a String using Set
In the last example, we have used HashMap to solve this problem. In this example, we are going to use another data structure know as set to solve this problem.
The set data structure doesn’t allow duplicates and lookup time is O(1) . Using this property we can easily return duplicate characters from a string in java.
Here are the steps –
i) Declare a set which holds the value of character type.
ii) Traverse a string and put each character in a string. If the character is already present in a set, it means it’s a duplicate character.
The time complexity of this approach is O(n) and it’s space complexity is also O(n).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
//Using set find duplicate letters in a string public class DuplicateCharacter { public static void printDuplicateUsingSet(String str) { //Declare set Set<Character> set = new HashSet<>(); //Traverse a string for (int i = 0; i < str.length(); i++) { Character ch = str.charAt(i); //If character is already present in a set if (set.contains(ch)) { System.out.println(ch); } else { set.add(ch); } } } public static void main(String[] args) { String str = "java"; //Method call printDuplicateUsingSet(str); } } |
Java program to reverse each words of a string
Video Tutorial
In this video tutorial, I have explained multiple approaches to solve this problem.
