Stacks & QueuesProblem 37 of 38

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

Brute Force
Time: O(n^2)
Space: O(n)
Optimal
Time: O(n)
Space: O(n)

Problem Statement

Given a stream of characters, find the first non-repeating character at each point in the stream. For each new character added, output the first character that appears only once in the stream so far. If no such character exists, output -1 or '#'.

Example:

Stream: "aabcbcd" After 'a': First non-repeating = 'a' After 'a': First non-repeating = -1 (both 'a's repeated) After 'b': First non-repeating = 'b' After 'c': First non-repeating = 'b' After 'b': First non-repeating = 'c' (b repeated) After 'c': First non-repeating = 'd' (c repeated) After 'd': First non-repeating = 'd' Output: "a" -> -1 -> "b" -> "b" -> "c" -> "d" -> "d"

Approach 1: Brute Force

Intuition

For each new character, scan through all characters seen so far and find the first one with count 1. Simple but inefficient for large streams.

Algorithm

  1. Maintain string of all characters seen
  2. Maintain frequency count for each character
  3. For each query:
    • Scan from beginning of string
    • Return first character with frequency 1
    • Return -1 if none found
java
import java.util.*;

public class StreamCharsBruteForce {
    private StringBuilder stream;
    private int[] freq;
    
    public StreamCharsBruteForce() {
        stream = new StringBuilder();
        freq = new int[26];
    }
    
    // O(n) per character
    public char getFirstNonRepeating(char c) {
        stream.append(c);
        freq[c - 'a']++;
        
        // Find first non-repeating
        for (int i = 0; i < stream.length(); i++) {
            char ch = stream.charAt(i);
            if (freq[ch - 'a'] == 1) {
                return ch;
            }
        }
        
        return '#';
    }
    
    public static void main(String[] args) {
        StreamCharsBruteForce sc = new StreamCharsBruteForce();
        String stream = "aabcbcd";
        
        System.out.println("Stream processing:");
        for (char c : stream.toCharArray()) {
            char result = sc.getFirstNonRepeating(c);
            System.out.println("After '" + c + "': First non-repeating = " + 
                (result == '#' ? -1 : result));
        }
    }
}

Complexity Analysis

  • Time Complexity: O(n^2) overall - O(n) per character for n characters
  • Space Complexity: O(n) for storing the stream

Approach 2: Optimal (Queue + Frequency Array)

Intuition

Use a queue to maintain the order of characters as they appear. The front of the queue is always a candidate for the first non-repeating character. When a character repeats, we don't need to remove it from queue immediately - just skip it when checking.

Algorithm

  1. Use queue to store characters in order
  2. Use frequency array to count occurrences
  3. For each new character:
    • Increment frequency
    • Add to queue
    • Pop from front while front has frequency > 1
    • Front of queue (if exists) is the answer
java
import java.util.*;

public class StreamChars {
    private Queue<Character> queue;
    private int[] freq;
    
    public StreamChars() {
        queue = new LinkedList<>();
        freq = new int[26];
    }
    
    // O(1) amortized per character
    public char getFirstNonRepeating(char c) {
        freq[c - 'a']++;
        queue.offer(c);
        
        // Remove repeating characters from front
        while (!queue.isEmpty() && freq[queue.peek() - 'a'] > 1) {
            queue.poll();
        }
        
        if (queue.isEmpty()) {
            return '#';
        }
        
        return queue.peek();
    }
    
    public static void main(String[] args) {
        StreamChars sc = new StreamChars();
        String stream = "aabcbcd";
        
        System.out.println("Stream processing:");
        for (char c : stream.toCharArray()) {
            char result = sc.getFirstNonRepeating(c);
            System.out.println("After '" + c + "': First non-repeating = " + 
                (result == '#' ? -1 : result));
        }
    }
}

Complexity Analysis

  • Time Complexity: O(n) overall - O(1) amortized per character (each char enters and exits queue at most once)
  • Space Complexity: O(26) = O(1) for frequency array + O(n) worst case for queue

Approach 3: Using LinkedHashMap (Ordered Map)

Intuition

Use a data structure that maintains insertion order and allows O(1) deletion. In some languages, LinkedHashMap or OrderedDict provides this. Keep only non-repeating characters in the map.

Algorithm

  1. Use ordered map to store first occurrence of each character
  2. Use frequency array to track counts
  3. When character repeats, remove from ordered map
  4. First entry in ordered map is the answer
java
import java.util.*;

public class StreamCharsLinked {
    private LinkedHashSet<Character> order;  // Non-repeating chars in order
    private Set<Character> repeated;
    
    public StreamCharsLinked() {
        order = new LinkedHashSet<>();
        repeated = new HashSet<>();
    }
    
    // O(1) per character
    public char getFirstNonRepeating(char c) {
        if (repeated.contains(c)) {
            // Already repeated, ignore
        } else if (order.contains(c)) {
            // Second occurrence - move to repeated
            order.remove(c);
            repeated.add(c);
        } else {
            // First occurrence
            order.add(c);
        }
        
        if (order.isEmpty()) {
            return '#';
        }
        
        return order.iterator().next();
    }
    
    public static void main(String[] args) {
        StreamCharsLinked sc = new StreamCharsLinked();
        String stream = "aabcbcd";
        
        System.out.println("Stream processing:");
        for (char c : stream.toCharArray()) {
            char result = sc.getFirstNonRepeating(c);
            System.out.println("After '" + c + "': First non-repeating = " + 
                (result == '#' ? -1 : result));
        }
    }
}

Complexity Analysis

  • Time Complexity: O(1) per character - all operations are O(1)
  • Space Complexity: O(26) = O(1) for alphabet-sized storage

Visual Walkthrough

Stream: "aabcbcd" After 'a': Queue: [a] Freq: {a:1} First non-repeating: 'a' After 'a': Queue: [a, a] → pop 'a' (freq > 1) → [] Freq: {a:2} First non-repeating: -1 After 'b': Queue: [b] Freq: {a:2, b:1} First non-repeating: 'b' After 'c': Queue: [b, c] Freq: {a:2, b:1, c:1} First non-repeating: 'b' After 'b': Queue: [b, c] → pop 'b' (freq > 1) → [c] Freq: {a:2, b:2, c:1} First non-repeating: 'c' After 'c': Queue: [c] → pop 'c' (freq > 1) → [] Queue: [d] (after adding d) Freq: {a:2, b:2, c:2} Wait, we haven't added 'd' yet! After 'c': Queue: [c, c] → pop both → [] Freq: {a:2, b:2, c:2} First non-repeating: -1 Actually, let me redo: After 'c' (second c): Queue: [c] → pop 'c' (freq > 1) → [] First non-repeating: -1 or wait for 'd' After 'd': Queue: [d] Freq: {a:2, b:2, c:2, d:1} First non-repeating: 'd'

Key Takeaways

  1. Queue for Order: Queue maintains the order in which non-repeating characters appeared
  2. Lazy Removal: Don't remove immediately when character repeats, check when needed
  3. Amortized Analysis: Each character enters and exits queue at most once → O(1) amortized
  4. Stream Processing: Pattern applicable to real-time data processing
  5. This is a classic interview problem testing queue and hash map usage
  6. Real-world use: Network packet analysis, log processing, real-time analytics
Previous
Minimum sum of squares of character counts in a given string after removing k characters
Next
Next Smaller Element