Question

link

Question One: Given a string, find the first non-repeating character in it

link

Question Two: Given a stream of characters, find the first non-repeating character from stream. You need to tell the first non-repeating character in O(1) time at any moment.

From a string

  1. Scan the string from left to right and construct the count array.

  2. Again, scan the string from left to right and check for count of each
    character, if you find an element who’s count is 1, return it.

O(n) time.

The array is size of 128 if it’s ASCII encoding. It can also be replaced with a HashMap if the length of the string is small.

From a stream of chars

Use a DLL (doubly linked list), 1 count array and 1 DLL-node array. Alternatively, the 2 arrays can be replaced with 2 HashMaps.

In totally, one DLL and 2 array are used. The DLL is used to get the sequence of non-repeating chars. The 1st array is for char count, and the 2nd array is for fast loop-up in the DLL.

The detailed precedure:

  1. Create an empty DLL and 2 arrays: repeated[] and dllMap[].

  2. To get the first non-repeating character, return the head of DLL.

  3. Following are steps to process a new character ‘x’ in stream.

    1. If repeated[x] is false and dllMap[x] is NULL, append x to DLL and store it in dllMap[x].

    2. If repeated[x] is false and dllMap[x] is not NULL, get DLL node of x using dllMap[x] and remove the node. Set repeated[x] as true and optionally clear dllMap[x].

    3. If repeated[x] is true, ignore it.

I didn’t write code for this question.