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

The problem, simply

Letters come in one by one, like a stream. After each new letter, look at everything that has arrived so far and find the first letter (in arrival order) that has appeared exactly once. Write it down, or write # if there is none.

For the stream a a b c the answer is a # b b. After the first a, it is a. After the second a, no letter is single. After b, it is b. After c, b is still the earliest single letter.

The letters are lowercase a to z, so there are only 26 kinds.

A story to remember it

Picture it

Examples

Way 1: the simple way

Keep a count for each letter and remember the whole stream. After each letter, scan the stream from the start and stop at the first letter whose count is 1.

1. Add the new letter to the stream and add 1 to its count.
2. Scan the stream from the start. The first letter with count 1 is the answer. If none, write #.

class Solution {
    public String FirstNonRepeating(String s) {
        int[] count = new int[26];
        StringBuilder out = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
            char ans = '#';
            for (int j = 0; j <= i; j++) {                 // scan from the start every time
                if (count[s.charAt(j) - 'a'] == 1) { ans = s.charAt(j); break; }
            }
            out.append(ans);
        }
        return out.toString();
    }
}

How long it takes: for each of the n letters we may scan all letters before it, O(n^2). Extra room: the answer and the counts, O(n) counting the answer.

Way 2: the clever way

Keep the line of the slide: a doubly linked list of letters seen exactly once, in arrival order. Next to it keep the notebook, an array of 26 slots that points at each letter's box in the line, plus a mark for letters that are out for good.

1. New letter: make a box and hang it at the back of the line. Write down where its box is.
2. Second time: the notebook says where the box is. Unhook it in one step, because a two way box knows both of its neighbors. Mark the letter as repeated.
3. Third time or more: the letter is already marked repeated. Do nothing.
4. After each letter, the answer is the front box of the line, or # if the line is empty.

class Solution {
    static class Box {
        char ch;
        Box prev, next;
        Box(char ch) { this.ch = ch; }
    }

    public String FirstNonRepeating(String s) {
        Box head = new Box('#'), tail = new Box('#');    // two guard boxes, never removed
        head.next = tail;
        tail.prev = head;
        Box[] where = new Box[26];                       // the notebook
        boolean[] repeated = new boolean[26];
        StringBuilder out = new StringBuilder();

        for (char c : s.toCharArray()) {
            int k = c - 'a';
            if (!repeated[k]) {
                if (where[k] == null) {                  // first time: join at the back
                    Box b = new Box(c);
                    b.prev = tail.prev;
                    b.next = tail;
                    tail.prev.next = b;
                    tail.prev = b;
                    where[k] = b;
                } else {                                 // second time: leave the line
                    Box b = where[k];
                    b.prev.next = b.next;                // neighbors hold hands
                    b.next.prev = b.prev;
                    where[k] = null;
                    repeated[k] = true;
                }
            }
            out.append(head.next == tail ? '#' : head.next.ch);
        }
        return out.toString();
    }
}

How long it takes: each letter does a fixed amount of work, O(n) in total. Extra room: at most 26 boxes and two arrays of 26, O(1), apart from the answer string.

Watch out for

• Removing from the middle of a one way list. You would need to walk to find the box before it, which costs O(26) per letter and is messy. The back arrows make it one step.
• Guard boxes at both ends remove all the "is this the first or last box" special cases.
• A bigger alphabet. Use a HashMap<Character, Box> instead of arrays. The room becomes the number of different letters.
• Writing the answer only at the end. The question wants one answer per letter of the stream.

What interviewers ask next

• Can you do it with a plain queue? Yes. Push every new letter at the back. Before answering, pop from the front while the front letter's count is more than 1. Each letter is pushed and popped at most once, so it is O(n) in total, though one single step can take longer.
• Why not just keep a count array and scan the 26 letters each time? You need arrival order, not alphabet order. You could store each letter's first arrival time and pick the smallest among count 1 letters: O(26) per step, also fine for a small alphabet.
• First unique character in a fixed string (LeetCode 387). Count first, then scan the string once. No streaming needed.
• LRU cache. The same building blocks: a doubly linked list for order and a hash map to find any box in O(1).

Remember this

Grown-up words: the stream is an online input, the line of kids is a doubly linked list, the notebook is a hash map (or array) from letter to node, the guard boxes are sentinel nodes, and the same pattern powers an LRU cache.