Find the first non-repeating character from a stream of characters | GeeksforGeeks

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.

The idea is to use a DLL (Doubly Linked List) to efficiently get the first non-repeating character from a stream. The DLL contains all non-repeating characters in order, i.e., the head of DLL contains first non-repeating character, the second node contains the second non-repeating and so on.
We also maintain two arrays: one array is to maintain characters that are already visited two or more times, we call it repeated[], the other array is array of pointers to linked list nodes, we call it inDLL[]. The size of both arrays is equal to alphabet size which is typically 256.
Also check http://algorithmsandme.blogspot.com/2014/07/find-first-non-repeating-character-in.html

1. Take the input character. Check in 'visited' array if this character is seen more than two time.
2. If yes, don't do anything, process next character.
3. If it not seen two times yet, then we need check if it is seen first time.
4. If seen first time, DDL node entry corresponding to that character will be null. Add node in DLL and update the hash table.
5. If character is already seen once, we will have a node entry in hash table. We will remove that node from queue and marked 'visited' entry as visited.

void findFirstNonRepeating()

{

    // inDLL[x] contains pointer to a DLL node if x is present in DLL.

    // If x is not present, then inDLL[x] is NULL

    struct node *inDLL[MAX_CHAR];

    // repeated[x] is true if x is repeated two or more times. If x is

    // not seen so far or x is seen only once. then repeated[x] is false

    bool repeated[MAX_CHAR];

    // Initialize the above two arrays

    struct node *head = NULL, *tail = NULL;

    for (int i = 0; i < MAX_CHAR; i++)

    {

        inDLL[i] = NULL;

        repeated[i] = false;

    }

    // Let us consider following stream and see the process

    char stream[] = "geeksforgeeksandgeeksquizfor";

    for (int i = 0; stream[i]; i++)

    {

        char x = stream[i];

        cout << "Reading " << x << " from stream \n";

        // We process this character only if it has not occurred or occurred

        // only once. repeated[x] is true if x is repeated twice or more.s

        if (!repeated[x])

        {

            // If the character is not in DLL, then add this at the end of DLL.

            if (inDLL[x] == NULL)

            {

                appendNode(&head, &tail, stream[i]);

                inDLL[x] = tail;

            }

            else // Otherwise remove this caharacter from DLL

            {

                removeNode(&head, &tail, inDLL[x]);

                inDLL[x] = NULL;

                repeated[x] = true;  // Also mark it as repeated

            }

        }

        // Print the current first non-repeating character from stream

        if (head != NULL)

            cout << "First non-repeating character so far is " << head->a << endl;

    }

}

From Coding Interviews: Questions, Analysis & Solutions
    CharStatistics() : index (0) {
        for(int i = 0; i < 256; ++i)
            occurrence[i] = -1;
    }
    void Insert(char ch) {
        if(occurrence[ch] == -1)
            occurrence[ch] = index;
        else if(occurrence[ch] >= 0)
            occurrence[ch] = -2;

        index++;
    }

    char FirstAppearingOnce() {
        char ch = '\0';
        int minIndex = numeric_limits<int>::max();
        for(int i = 0; i < 256; ++i) {
            if(occurrence[i] >= 0 && occurrence[i] < minIndex) {
                ch = (char)i;
                minIndex = occurrence[i];
            }
        }

        return ch;
    }
http://n00tc0d3r.blogspot.com/2013/08/find-first-non-repeating-character-in.html
use a HashMap to track the occurrence of each letter.
We iterate through the string twice: the first one is to compute the occurrences; and the second one is to find the first letter with occurrence = 1.
This algorithm runs in time O(2n)=O(n) and takes O(n) spaces.
public static Character findFirstUnique(String s) {
   // map: char -- occurrence
   HashMap<Character, Integer> map = new HashMap<Character, Integer>();

   // loop 1: compute occurrence
   for (int i=0; i<s.length(); ++i) {
     char c = s.charAt(i);
     if (map.containsKey(c)) {
       map.put(c, map.get(c)+1);
     } else {
       map.put(c, 1);
     }
   }

   // loop 2: find the first unique
   for (int i=0; i<s.length(); ++i) {
     char c = s.charAt(i);
     if (map.get(c) == 1) return c;
   }

   return null;
 }

Do we have to iterate through the entire string twice? For a string like "aaaaaaaaeeeeeeeeeeddddddddf", if we can avoid revisiting all of the duplicates, the running time will be improved (still the same order though).

So, ideally, besides the hashmap for occurrences, if we could have a data structure to store the known unique letters in order and remove ones that have at least one duplicates, then at the end of the first loop the first element is what we are looking for.
What we need for the data structure are:

• O(1) time for operations like insert, remove, contains
• elements are in insertion order

LinkedHashSet seems to be a good option here. LinkedHashSet can be thought as HashSet plus Doubly Linked List.
We can just use hashset, as don't need to contains count. 

public Character findFirstUnique(String s) {  
   // map: char -- occurrence  
   HashMap<Character, Integer> map = new HashMap<Character, Integer>();  
   LinkedHashSet<Character> set = new LinkedHashSet<Character>(s.length());  

   // loop: compute occurrence  
   for (int i=0; i<s.length(); ++i) {  
     char c = s.charAt(i);  
     if (map.containsKey(c)) {  
       set.remove(c);  
     } else {  
       map.put(c, 1);  
       set.add(c);  
     }  
   }  

   // find the first unique in the ordered set  
   Iterator<Character> it = set.iterator();  
   if (it.hasNext()) return it.next();  
   return null;  
 }  

Using LinkedHashMap to find first non repeated character of String
When we need maintain order(such as get first...), consider using LinkedHashMap.\\
http://javarevisited.blogspot.com/2014/03/3-ways-to-find-first-non-repeated-character-String-programming-problem.html

    public static char getFirstNonRepeatedChar(String str) {
        Map<Character,Integer> counts = new LinkedHashMap<>(str.length());
        
        for (char c : str.toCharArray()) {
            counts.put(c, counts.containsKey(c) ? counts.get(c) + 1 : 1);
        }
        
        for (Entry<Character,Integer> entry : counts.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        throw new RuntimeException("didn't find any non repeated Character");
    }

===> we should use LinkedHashset, not List for nonRepeating.

    /*
     * Finds first non repeated character in a String in just one pass.
     * It uses two storage to cut down one iteration, standard space vs time
     * trade-off.Since we store repeated and non-repeated character separately,
     * at the end of iteration, first element from List is our first non
     * repeated character from String.
     */
    public static char firstNonRepeatingChar(String word) {
        Set<Character> repeating = new HashSet<>();
        List<Character> nonRepeating = new ArrayList<>();
        for (int i = 0; i < word.length(); i++) {
            char letter = word.charAt(i);
            if (repeating.contains(letter)) {
                continue;
            }
            if (nonRepeating.contains(letter)) {
                nonRepeating.remove((Character) letter); // this is O(n), 
                repeating.add(letter);
            } else {
                nonRepeating.add(letter);
            }
        }
        return nonRepeating.get(0);
    }

http://hehejun.blogspot.com/2015/01/algorithmfirst-non-repeating-character.html
一个很简单的方法就是扫两遍string，第一遍记录每一个字符的数量，更新map，第二次从左往右找到第一个出现次数是1的即可。但是当string很长的时候two-pass的方法效率不是很好，如果要求one-pass的话，我们第二遍扫map即可，因为当string很长是，相对于string，map的长度是很小的，所以我们在存map的时候，除了存count还需要把第一次出现的index也存下来
private class Counter {
private int count; //
private int index;

public Counter(int index) {
count = 1;
this.index = index;
}
}

public char find(String s) {
if (s == null)
return ' ';
int len = s.length();
HashMap<Character, Counter> map = new HashMap<Character, Counter>();
for (int i = 0; i < len; i++) {
if (!map.containsKey(s.charAt(i)))
map.put(s.charAt(i), new Counter(i));
else
map.get(s.charAt(i)).count++;
}
Iterator<Entry<Character, Counter>> iter = map.entrySet().iterator();
int index = Integer.MAX_VALUE;
char res = ' ';
while (iter.hasNext()) {
Entry<Character, Counter> entry = iter.next();
if (entry.getValue().count == 1 && entry.getValue().index < index) {
index = entry.getValue().index;
res = entry.getKey();
}
}
return res;
}
Read full article from Find the first non-repeating character from a stream of characters | GeeksforGeeks