The 'First Non-Repeating Character' problem is a fundamental algorithmic challenge frequently encountered in technical coding interviews and real-time stream processing systems. The objective is to efficiently identify the first unique character in a string with optimal time and space complexity.

1. Problem Definition & Constraints

Given a string s consisting of lowercase Latin letters (a–z), return the first character that appears exactly once. If every character in the string repeats, return '$' (or -1 depending on caller specification).

2. Two-Pass Frequency Array Algorithm (C++ Implementation)

Because the character set is strictly constrained to lowercase English letters (26 characters), an array of fixed size 26 yields superior cache locality compared to a dynamic hash table:

#include <iostream>
#include <string>
#include <vector>

char firstNonRepeatingChar(const std::string& s) {
    // Frequency table for 26 lowercase English letters
    std::vector<int> freq(26, 0);

    // Pass 1: Tally frequencies
    for (char c : s) {
        freq[c - 'a']++;
    }

    // Pass 2: Identify first character with frequency == 1
    for (char c : s) {
        if (freq[c - 'a'] == 1) {
            return c;
        }
    }

    return '$';
}

int main() {
    std::string s = "geeksforgeeks";
    char result = firstNonRepeatingChar(s);
    std::cout << "First unique char: " << (result == '$' ? "-1" : std::string(1, result)) << std::endl;
    return 0;
}

3. Single-Pass Stream Processing Approach (Queue / Doubly-Linked List)

When processing characters arriving over a continuous network socket stream where the full string cannot be stored in memory, a combination of a frequency array and a FIFO queue ensures $O(1)$ amortized lookup per incoming character:

function findFirstUniqueInStream(stream: Iterable<string>): string[] {
    const freq = new Map<string, number>();
    const queue: string[] = [];
    const results: string[] = [];

    for (const char of stream) {
        freq.set(char, (freq.get(char) || 0) + 1);
        queue.push(char);

        // Evict repeating characters from the front of the queue
        while (queue.length > 0 && (freq.get(queue[0]) || 0) > 1) {
            queue.shift();
        }

        results.push(queue.length > 0 ? queue[0] : '-1');
    }

    return results;
}

4. Complexity Analysis

• Time Complexity: $O(N)$ where $N$ is the length of the string. Pass 1 takes $O(N)$ to tally frequencies, and Pass 2 takes $O(N)$ in the worst case.
• Space Complexity: $O(1)$ auxiliary memory since the frequency array size is bounded by the constant alphabet size (Σ = 26).