First Unique Character in a Stream

hard Java Collections

Letters arrive one per line. After each new letter, print the first letter (in order of arrival) that has appeared exactly once so far, or none if there is no such letter. Use a count map and a queue of candidates, so that each letter is handled in O(1) on average.

Constraints

1 <= lines <= 10^5
each line is one lowercase letter

Examples

Input

a
a
b
c

Output

a
none
b
b

Queue
Hash map
Streaming algorithms

Solutions

Best approachTime O(n)Space O(n)

Scanning all letters after each arrival would cost O(n^2). A letter that has repeated can never be unique again, so we remove it from the queue for good; every letter enters and leaves the queue at most once, giving O(n) in total.

Same code works in Java810172125Basic features only, so nothing changes between versions.

/*
 * Problem : Process lines.
 * Input   : Several lines.
 * Output  : One answer per letter.
 * Approach: A stream of letters.
 * Time    : O(n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(String[] lines) {
        // Step 1: "counts" tells how many times each letter appeared. The queue holds letters that may still be unique.
        java.util.Map<String, Integer> counts = new java.util.HashMap<>();
        java.util.ArrayDeque<String> candidates = new java.util.ArrayDeque<>();
        String[] output = new String[lines.length];
        for (int i = 0; i < lines.length; i++) {
            String letter = lines[i];
            counts.merge(letter, 1, Integer::sum);
            candidates.addLast(letter);
            // Step 2: Remove letters from the front while they are not unique any more.
            while (!candidates.isEmpty() && counts.get(candidates.peekFirst()) > 1) {
                candidates.pollFirst();
            }
            // Step 3: The front of the queue is the first unique letter.
            output[i] = candidates.isEmpty() ? "none" : candidates.peekFirst();
        }
        return output;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        java.util.List<String> all = new java.util.ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (!line.isEmpty()) {
                all.add(line);
            }
        }
        String[] lines = all.toArray(new String[0]);
        System.out.println(String.join("\n", solve(lines)));
    }
}

Hints (1)

Why can a removed letter never come back as the answer?