Find the first non-repeating character in a stream of characters.
Given a string A denoting a stream of lowercase alphabets. We have to write a code to make a new string B.
Here is the rule to form string B.
i) We have to find the first non-repeating character each time a character is inserted into the stream and append it at the end to B.
ii) If no non-repeating character is found then append ‘#’ at the end of B.
For example –
Example 1 –
Input = “abadbc”
Output = “aabbdd”
Explanation:
“a” – From the stream, the first character is a, So at this point, the first non-repeating character is ‘a’.
“ab” – When b comes, Still the first non-repeating character is ‘a’.
“aba” – This time the character is a. Character a is repeated twice so the first non repeating character is ‘b’
“abad” – When character d comes, the first non-repeating character is ‘b’.
“abadb” – When character b comes, its count is 2 now. So the first non-repeating character at this point is ‘d’.
“abadbc” – Next character is c. At this point, the first non-repeating character is ‘d’.
Example 2 –
Input = “abdabd”
Output = “aaabd#”
We have discussed the problem statement. The next question is how do we approach this problem? Which data structure should we use?
The easiest version of this problem is to find first non-repeating character in a string. When the complete string is given instead of one character is coming at a time from the stream, then we can easily solve the problem using HashMap.
In this case, We can’t be able to solve a problem by simply using HashMap. We need another data structure to maintain the character order.
Also, I have shared the video tutorial link at the end of this post.
First Non Repeating Character in a Stream of Characters – Java Code
In this example, I am going to example how we can solve this problem using HashMap and Queue data structure.
Here are the following steps –
i) When a character comes from the stream, we put the character and its count in a HashMap. Also, we enqueue that character in a queue.
ii) If its count is 1, then we append that character in a new string. Else we poll the queue until we found the character whose count is 1. If a queue is empty then we append #.
|
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 45 46 47 48 49 50 51 |
//First non-repeating character in a stream of characters public class NonRepeatingStream { public static String nonRepeatingCharacter(String A) { StringBuilder ans = new StringBuilder(); Queue<Character> queue = new LinkedList<>(); Map<Character, Integer> charCountMap = new HashMap<>(); for(int i = 0; i < A.length(); i++) { char c = A.charAt(i); //put character and it's count in a map charCountMap.put(c, charCountMap.getOrDefault(c, 0)+1); //Add them in a queue queue.add(c); //While queue is not empty while(!queue.isEmpty()) { if(charCountMap.containsKey(queue.peek()) && charCountMap.get(queue.peek()) > 1) { queue.poll(); } else { break; } } if(queue.isEmpty()) { ans.append('#'); } else { ans.append(queue.peek()); } } return ans.toString(); } public static void main(String[] args) { String str = "aabadbc"; String result = nonRepeatingCharacter(str); System.out.println(result); } } |
Find first non-repeating character in a stream of characters video tutorial
