Log inSign up
easyGeeksforGeeksNot Started

First Non-Repeating Character in a Stream

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Queue
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an input stream A of n characters consisting only of lowercase alphabets. While reading characters from the stream, you have to tell which character has appeared only once in the stream upto that point. If there are many such characters you have to tell the first character based on its appearance in the stream. If there is no such character, append # to the result.

Return a string containing the first non-repeating character after each input character.

Example 1 · Standard Stream Example:

Input: A = "aabc"
Output: "a#bb"
Explanation: Step 1: "a" -> non-repeating: "a" Step 2: "aa" -> non-repeating: none ("#") Step 3: "aab" -> non-repeating: "b" Step 4: "aabc" -> non-repeating: "b" Result: "a#bb"

Example 2 · All Repeating Characters:

Input: A = "zz"
Output: "z#"
Explanation: Step 1: "z" -> "z" Step 2: "zz" -> "#"

Constraints:

  • 1 <= n <= 105
  • a <= A[i] <= z

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Frequency Array / Hash Map
  • Queue FIFO Eviction

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Combine FIFO Queues with Hash/Frequency tracking for stream filtering.
  • Apply lazy deletion (purging stale items only when they reach the front of the queue).
  • Understand the 26-character alphabet constant-space bound O(1).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Real-time stream evaluation of earliest unique elements.
  • Need O(1) query time for the first arrival among valid items.

Algorithmic Decision Tree:

  • Increment freq[ch - 'a'].
  • Push ch to FIFO queue.
  • While !q.empty() and freq[q.front() - 'a'] > 1, pop q.
  • Append q.empty() ? '#' : q.front().

Connected Patterns:

Number of Recent CallsMoving Average from Data StreamFirst Unique Character in a String

1. Brute Force — Prefix Re-Scan (O(N^2))

Intuition

Maintain character frequencies. For each index i, iterate from 0 to i and find the first character with freq == 1.

Algorithm

  1. Step 1: Iterate through each character A[i].
  2. Step 2: Update frequency of A[i].
  3. Step 3: Scan A[0...i] to find the first character with count == 1.
  4. Step 4: Append found character, or # if none found.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5using namespace std;
6
7class Solution {
8public:
9 string FirstNonRepeating(string A) {
10 string res = "";
11 vector<int> freq(26, 0);
12
13 for (int i = 0; i < A.size(); ++i) {
14 freq[A[i] - 'a']++;
15 char nonRep = '#';
16 for (int j = 0; j <= i; ++j) {
17 if (freq[A[j] - 'a'] == 1) {
18 nonRep = A[j];
19 break;
20 }
21 }
22 res += nonRep;
23 }
24 return res;
25 }
26};
27
28int main() {
29 Solution sol;
30 cout << sol.FirstNonRepeating("aabc") << endl; // a#bb
31 cout << sol.FirstNonRepeating("zz") << endl; // z#
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(N^2) — For each character, scans the entire prefix to find the first character with count 1.
  • Space complexity: O(1) — Uses frequency array of size 26.

Why Brute Force Doesn't Scale:

A stream of 105 characters requires 5 x 109 operations.

Queue with frequency array processes 105 characters in 12ms.

2. Better — Doubly Linked List with Fast Node Removal

Intuition

Maintain active unique characters in a Doubly Linked List. On first appearance, append to DLL. On second appearance, remove node from DLL in O(1).

Algorithm

  1. Step 1: Track inDLL[26] node pointers and repeated[26] booleans.
  2. Step 2: If character is seen for the first time, append node to DLL.
  3. Step 3: If character is seen again, remove its node from DLL and mark repeated.
  4. Step 4: The head of the DLL is the first non-repeating character.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5using namespace std;
6
7struct CharNode {
8 char ch;
9 CharNode* prev;
10 CharNode* next;
11 CharNode(char c) : ch(c), prev(nullptr), next(nullptr) {}
12};
13
14class Solution {
15public:
16 string FirstNonRepeating(string A) {
17 string res = "";
18 vector<CharNode*> inDLL(26, nullptr);
19 vector<bool> repeated(26, false);
20
21 CharNode* head = new CharNode(' ');
22 CharNode* tail = new CharNode(' ');
23 head->next = tail;
24 tail->prev = head;
25
26 auto removeNode = [](CharNode* node) {
27 node->prev->next = node->next;
28 node->next->prev = node->prev;
29 delete node;
30 };
31
32 for (char c : A) {
33 int idx = c - 'a';
34 if (!repeated[idx]) {
35 if (inDLL[idx] == nullptr) {
36 CharNode* node = new CharNode(c);
37 node->prev = tail->prev;
38 node->next = tail;
39 tail->prev->next = node;
40 tail->prev = node;
41 inDLL[idx] = node;
42 } else {
43 removeNode(inDLL[idx]);
44 inDLL[idx] = nullptr;
45 repeated[idx] = true;
46 }
47 }
48 res += (head->next == tail) ? '#' : head->next->ch;
49 }
50 return res;
51 }
52};
53
54int main() {
55 Solution sol;
56 cout << sol.FirstNonRepeating("aabc") << endl; // a#bb
57 return 0;
58}

Time & Space Complexity

  • Time complexity: O(N) — Direct pointer deletion from DLL in O(1) on second appearance.
  • Space complexity: O(1) (26 nodes max) — At most 26 DLL nodes.

3. Optimal — Frequency Array with FIFO Queue Eviction

Intuition

Count frequencies in freq[26]. Push each incoming character to a queue. Discard front elements with frequency > 1 lazily.

Algorithm

  1. Step 1: Initialize frequency array freq[26] = {0} and empty queue q.
  2. Step 2: For each character c in A:
  3. Step 3: Increment freq[c - 'a']++ and push c to q.
  4. Step 4: While !q.empty() and freq[q.front() - 'a'] > 1, pop q.
  5. Step 5: Append q.empty() ? '#' : q.front() to result string.

Queue Eviction Frequency Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
freq[a]=1
Visual state
Values and pointers at this exact step
queue
FRONT → REAR
a (count=1)
Enqueue adds at the rear · Dequeue removes from the front
Decision / next transition
Push "a"
Why this step matters

freq[a]=1. Front is "a". Append "a".

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <queue>
5
6using namespace std;
7
8class Solution {
9public:
10 string FirstNonRepeating(string A) {
11 string res = "";
12 vector<int> freq(26, 0);
13 queue<char> q;
14
15 for (char c : A) {
16 freq[c - 'a']++;
17 q.push(c);
18
19 while (!q.empty() && freq[q.front() - 'a'] > 1) {
20 q.pop();
21 }
22
23 if (q.empty()) {
24 res += '#';
25 } else {
26 res += q.front();
27 }
28 }
29 return res;
30 }
31};
32
33int main() {
34 Solution sol;
35 cout << sol.FirstNonRepeating("aabc") << endl; // a#bb
36 cout << sol.FirstNonRepeating("zz") << endl; // z#
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N) Total (Amortized O(1) per character) — Every unique character enters the queue once and is popped at most once. Over N characters, total time is O(N).
  • Space complexity: O(1) Auxiliary Space (At most 26 queue elements) — The queue holds at most 26 unique lowercase English letters at any point.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Scan Prefix on Every CharacterO(N^2)O(1) (26 alphabet counts)For each prefix of length i, scan from index 0 to i and find the first character with frequency 1.Re-scanning previous characters repeatedly.
2.Better — Doubly Linked List + Map (LRU Style)O(N)O(1) (26 nodes max)Use a DLL where each node represents an active unique character, and an array of pointers to delete nodes upon second occurrence.Pointer complexity.
3.Optimal — Frequency Array + FIFO Queue EvictionOptimalO(N) Total (Amortized O(1) per char)O(1) (26 max queue size)Increment frequency, push to queue, and pop stale duplicate characters from front.None. Each alphabet character is popped at most once.

Common Pitfalls & Crucial Edge Cases

Checking frequency only on insert

Characters pushed earlier can become duplicates later; you must check freq[q.front()] > 1 inside a while loop, not an if.

Re-scanning the queue from scratch

Only the front needs to be verified; if the front has frequency 1, it is guaranteed to be the earliest non-repeating character.

Crucial Edge Cases to Validate:

  • All characters distinct (e.g. 'abcdef') — Front element remains a for entire stream.
  • All characters repeating (e.g. 'aabbcc') — Outputs alternating character followed by # (a#b#c#).
  • Single character string — Returns that character directly.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight lazy deletion: 'We don't need to search and remove from the middle of the queue; we only purge when the duplicate reaches the front.'
  2. Explain alphabet bounds: 'Because the character set is bounded by 26, space is strictly O(1).'
  3. Point out that lazy queue eviction works in amortized O(1) time because each character is popped at most once.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the space complexity of the optimal queue approach O(1)?

2.Why can an expired character be safely popped from the queue forever?

3.What is the amortized time cost per character in the stream?

Back to DSA Sheet