PROBLEM DESCRIPTION
Given an input stream A of n characters consisting only of lower case alphabets. While reading characters from the stream, you have to tell which character has appeared only once in the stream upto that point. If there are many characters that have appeared only once, you have to tell which one of them was the first one to appear. If there is no such character then append # to the answer.
NOTE:
- You need to find the answer for every
i(0 <= i < n) - In order to find the solution for every
iyou need to consider the string from starting position till ith position.
SOLUTION
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
52
53
54
55
class Solution
{
public String FirstNonRepeating(String A)
{
// Doubly linked list to store characters in the order they appear
LinkedList<Character> dll = new LinkedList<>();
// Set to keep track of characters that have already appeared
// We can also use an array of size 26 to check this
Set<Character> set = new HashSet<>();
// StringBuffer to store the result
StringBuffer sb = new StringBuffer();
// Length of the input stream
int n = A.length();
// Loop through each character in the input stream
for(int i=0; i<n; i++){
// Get the current character
char ch = A.charAt(i);
// If the character is not already in the set (hasn't appeared before)
if(!set.contains(ch)){
// Add the character to the doubly linked list
// The answer needs to be the first non-repeating character. If that duplicates, then the next one can become the answer
dll.add(ch);
// Add the character to the set to mark it as appeared
set.add(ch);
}
else{
// If the character has appeared before, remove it from the doubly linked list
// This will take O(N) time to remove a certain node from the DLL
// This can be optimized by using HashMap to get a direct reference to the node corresponding to a given character
dll.remove(Character.valueOf(ch));
}
// If there are no non-repeating characters, append '#' to the result
if(dll == null || dll.size() == 0)
sb.append("#");
// Otherwise, append the first non-repeating character to the result
else
sb.append(dll.getFirst());
}
return sb.toString();
}
}