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

Java

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.