Stream First Non-Repeating Character

Problem Summary

This is a classic streaming + queue + frequency problem.

Given a string s, for each index i, you must find:

• The first non-repeating character in prefix s[0..i]

• If none exists → return '#'

Key Insight

We need:

• Frequency tracking → to know repetition

• Order tracking → to know “first seen”

So we use:

• Queue → maintains order of characters

• count[] → frequency array

Idea

For each character:

• Increase its frequency

• Add to queue

• Remove all characters from front of queue if they are repeating

• Queue front = answer

Algorithm

For each character c:

• count[c]++

• push into queue

• while queue front is repeating → remove it

• if queue empty → add #

• else → add queue front

Example

Input:

aabc

Step-by-step:

• Prefix: a

  • Queue: a

  • Answer: a

• Prefix: aa

  • Queue: empty

  • Answer: #

• Prefix: aab

  • Queue: b

  • Answer: b

• Prefix: aabc

  • Queue: b

  • Answer: b

Output:

a#bb

Java Solution

import java.util.*;

class Solution {
    public String firstNonRepeating(String s) {

        int[] freq = new int[26];
        Queue<Character> q = new LinkedList<>();

        StringBuilder ans = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {

            char ch = s.charAt(i);

            // update frequency
            freq[ch - 'a']++;

            // add to queue
            q.add(ch);

            // remove all repeating characters from front
            while (!q.isEmpty() && freq[q.peek() - 'a'] > 1) {
                q.poll();
            }

            // append result
            if (q.isEmpty()) {
                ans.append('#');
            } else {
                ans.append(q.peek());
            }
        }

        return ans.toString();
    }
}

Complexity

• Time Complexity: O(n)
  (each character enters and leaves queue at most once)

• Space Complexity: O(1)
  (fixed 26 frequency array + queue)

Key Takeaways

• Use queue for order

• Use frequency array for repetition check

• Classic streaming problem pattern

• Very common in interviews (Amazon, Microsoft, Adobe)

Pattern Recognition

If you see:

• “stream of characters”

• “first non-repeating so far”

• “dynamic prefix answer”

Think:

Queue + Frequency Map

Summary

This problem demonstrates how to efficiently process a stream of characters by combining a queue for maintaining order and a frequency array for tracking repetition. By continuously updating both structures, we can determine the first non-repeating character at each step in linear time.