First Unique Character In A String

A character is said to be non-repeating if its frequency in the string is unit. To find such characters, one needs to find the frequency of all characters in the string and check which character has a unit frequency. This task could be done efficiently using a count array to map the character to their respective frequencies. We can simultaneously update the frequency of any character we come across in constant time. The maximum distinct characters in the ASCII system are 256. So the count array has a maximum size of 256. Now read the string again, and the first character we find has a frequency as unity is the answer.

Below is the algorithm:

1. Make a count array that will map the character to their respective frequencies.
2. Traverse the given string.
3. Increase the count of the current character in the count array.
4. Now traverse the string again and check whether the current character has frequency=1.
5. If the frequency>1, continue the traversal.
6. Else break the loop and add the current character in the arraylist.

Make a count array to store the index of the character if it appears only once; else, it stores a negative value. So when it comes to finding the first non-repeating character, we have to scan the count array instead of the string.

Below is the algorithm:

1. Make a count array and initialize all characters by -1, i.e., all considered as absent.
2. Traverse the given string, and the value of count[x] will be the index of ‘x’ if ‘x’ appears only once. Else, the value is going to be either -1 or -2.
3. Now, traverse the count array and check if the ith character occurs only once (count[i] has a positive value) and appears before the current result, then update the result.
4. Add the character present at the result index in the arraylist.

We can use a Doubly Linked List to get the first non-repeating character from a stream efficiently. This can be done by storing all non-repeating characters in DLL. We will keep them in order, i.e., the head node of DLL contains the first non-repeating character, and the next node contains the next non-repeating character, and so on. We will also maintain two ArrayLists: the first one maintains characters that are already visited two or more times, the second one is stores pointers to linked list nodes.

Following is the algorithm to implement the above logic:

1. Create an empty doubly linked list DLL, a boolean array ISCHARREPEATED of size 256, and another ArrayList RESULT. In DLL, we store pointers to DLL nodes.
2. For all characters CH, ISCHARREPEATED[CH] is true if x is repeated two or more times, otherwise false. DLL[CH] contains a pointer to a DLL node if the character CH is present in DLL, otherwise NULL.
3. Initialize all values of DLL as NULL and ISCHARREPEATED[] as false.
4. To get the first non-repeating character, return the character at the head of DLL.
5. Iterate over given stream of characters, for each 0 ≤ i ≤ STREAM.LENGTH() and do:
   1. Initialize character TEMP to STREAM[i].
   2. Process 'TEMP' only if it has occurred at most once, i.e., if ISCHARREPEATED[TEMP] is false, add TEMP to DLL  if DLL does not contain TEMP. Else remove TEMP from DLL and make ISCHARREPEATED[TEMP] false.
6. Add the current first non-repeating character from the stream in the resultant ArrayList RESULT.
7. Return RESULT.