Queue based approach or first non-repeating character in a stream

The problem, simply

Letters come in one at a time, like a stream. After each new letter, answer this: among all the letters so far, which is the first one (the earliest to arrive) that has appeared exactly once? If no letter has appeared exactly once, answer #.

Give back all the answers as one string, one character per arriving letter. The examples put spaces between the answers only to make them easy to read.

A story to remember it

Picture it

Examples

Way 1: the simple way

Keep every letter of the stream and a count for each letter. After each new letter, walk the stream from the start and stop at the first letter whose count is 1.

1. Append the letter to seen and add 1 to its count.
2. Walk seen from the start. The first letter with count 1 is the answer.
3. If none, the answer is #.

class Solution {
    public String firstNonRepeating(String stream) {
        int[] count = new int[26];
        StringBuilder seen = new StringBuilder();
        StringBuilder out = new StringBuilder();
        for (char c : stream.toCharArray()) {
            count[c - 'a']++;
            seen.append(c);
            char ans = '#';
            for (int j = 0; j < seen.length(); j++) {      // walk from the very start
                if (count[seen.charAt(j) - 'a'] == 1) { ans = seen.charAt(j); break; }
            }
            out.append(ans);
        }
        return out.toString();
    }
}

How long it takes: after the ith letter we may walk all i letters, so O(n^2) in total. Extra room: the stored stream, O(n).

Way 2: the clever way

Keep a waiting line, a queue, of letters in the order they first arrived, plus a count for each letter.

1. A letter arrives. Add 1 to its count. If this is its first time, put it at the back of the queue.
2. Clean the front: while the letter at the front has a count above 1, remove it. Repeated letters in the middle can wait; they are removed when they reach the front.
3. The front of the queue is the answer. If the queue is empty, the answer is #.

import java.util.*;

class Solution {
    public String firstNonRepeating(String stream) {
        int[] count = new int[26];
        Queue<Character> line = new ArrayDeque<>();
        StringBuilder out = new StringBuilder();
        for (char c : stream.toCharArray()) {
            if (++count[c - 'a'] == 1) line.offer(c);        // first time: join the back
            while (!line.isEmpty() && count[line.peek() - 'a'] > 1) {
                line.poll();                                  // the front repeats: send it away
            }
            out.append(line.isEmpty() ? '#' : line.peek());
        }
        return out.toString();
    }
}

How long it takes: each letter joins the queue at most once and leaves at most once, so all the cleaning together is O(n), and the whole stream is O(n). Extra room: the queue holds each letter at most once, so at most 26 letters, O(1) for a fixed alphabet. The answer string itself is O(n).

Another way: a linked set with no waiting

If you want every step to be O(1) even in the worst case, keep the unique letters in a LinkedHashSet, which remembers insertion order and can remove any letter right away. Keep a second set of letters that have repeated.

import java.util.*;

class Solution {
    public String firstNonRepeating(String stream) {
        Set<Character> unique = new LinkedHashSet<>();   // seen once, in arrival order
        Set<Character> repeated = new HashSet<>();
        StringBuilder out = new StringBuilder();
        for (char c : stream.toCharArray()) {
            if (repeated.contains(c)) {
                // already out of the race
            } else if (unique.remove(c)) {
                repeated.add(c);                          // second time: drop it now
            } else {
                unique.add(c);                            // first time
            }
            out.append(unique.isEmpty() ? '#' : unique.iterator().next());
        }
        return out.toString();
    }
}

Inside, LinkedHashSet is a hash map plus a doubly linked list, the same pair used by an LRU cache.

Watch out for

• Putting a letter into the queue every time it arrives. It still works, but the queue grows to n instead of at most 26.
• Forgetting the # case when the queue is empty.
• Letters outside a to z. Use an int[256] or a HashMap for counts if the stream can have any character.

What interviewers ask next

• The stream is huge and has any Unicode character. Use a HashMap for counts. The queue idea stays the same.
• First unique character in a fixed string, not a stream. Count everything first, then walk the string once and return the first letter with count 1.
• Return the k-th unique letter at each step. With the linked set, walk k steps from its start. With a doubly linked list plus a map, you can keep a pointer for it.
• Why is Way 2 O(n) if there is a loop inside a loop? Each letter is removed at most once in the whole run. Count total removals, not removals per step. This is amortized analysis.

Remember this

Grown-up words: the stream is an online input, the line of unique kids is a queue, the tally marks are a frequency array, cleaning only the front is lazy deletion, and "each letter leaves at most once" is amortized O(1) per step.