LinkedListProblem 36 of 36

Find the first non-repeating character from a stream of characters

Find the First Non-Repeating Character from a Stream of Characters

Problem Statement

Given a stream of characters, find the first non-repeating character at any point. If no non-repeating character exists, return a special character (like '#' or '-1'). Design a system that can efficiently process characters as they arrive.

Example

Stream: a, a, b, c, b, d, d After 'a': First non-repeating = 'a' After 'a': First non-repeating = '#' (no non-repeating) After 'b': First non-repeating = 'b' After 'c': First non-repeating = 'b' After 'b': First non-repeating = 'c' After 'd': First non-repeating = 'c' After 'd': First non-repeating = 'c' Output: [a, #, b, b, c, c, c]

Brute Force Approach

Intuition

For each query, scan through all characters seen so far and find the first one with count = 1.

Algorithm

  1. Maintain a string/list of all characters received
  2. For each character, also maintain its count
  3. When queried, scan from the beginning to find first character with count = 1

Code

java
import java.util.HashMap;
import java.util.Map;
import java.util.ArrayList;
import java.util.List;

class FirstNonRepeatingBrute {
    private List<Character> stream;
    private Map<Character, Integer> count;
    
    public FirstNonRepeatingBrute() {
        stream = new ArrayList<>();
        count = new HashMap<>();
    }
    
    public void add(char ch) {
        stream.add(ch);
        count.put(ch, count.getOrDefault(ch, 0) + 1);
    }
    
    public char getFirstNonRepeating() {
        for (char c : stream) {
            if (count.get(c) == 1) {
                return c;
            }
        }
        return '#';
    }
    
    public static void main(String[] args) {
        FirstNonRepeatingBrute solver = new FirstNonRepeatingBrute();
        String input = "aabcbdd";
        
        System.out.println("Stream processing:");
        for (char c : input.toCharArray()) {
            solver.add(c);
            System.out.println("After '" + c + "': First non-repeating = " 
                             + solver.getFirstNonRepeating());
        }
    }
}

Complexity Analysis

  • Time Complexity: O(n) per query, O(n²) total for n characters
  • Space Complexity: O(n) for storing the stream

Optimal Approach (Doubly Linked List + HashMap)

Intuition

Use a Doubly Linked List (DLL) to maintain the order of non-repeating characters. Use a HashMap to track:

  1. Whether a character is repeated
  2. Pointer to its node in the DLL (if it exists)

When a character arrives:

  • If new: add to DLL tail and HashMap
  • If second occurrence: remove from DLL, mark as repeated
  • If already repeated: ignore

The head of DLL is always the first non-repeating character.

Algorithm

  1. Create an empty DLL and a HashMap
  2. For each character in stream:
    • If not seen: create node, add to DLL tail, add to HashMap
    • If seen once: remove from DLL, update HashMap to mark repeated
    • If already repeated: do nothing
  3. Query: return DLL head's data (or '#' if empty)

Code

java
import java.util.HashMap;
import java.util.Map;

class DLLNode {
    char data;
    DLLNode prev;
    DLLNode next;
    
    DLLNode(char c) {
        this.data = c;
        this.prev = null;
        this.next = null;
    }
}

class FirstNonRepeatingOptimal {
    private DLLNode head;
    private DLLNode tail;
    private Map<Character, DLLNode> charToNode;
    private Map<Character, Integer> count;
    
    public FirstNonRepeatingOptimal() {
        head = null;
        tail = null;
        charToNode = new HashMap<>();
        count = new HashMap<>();
    }
    
    private void removeNode(DLLNode node) {
        if (node.prev != null) {
            node.prev.next = node.next;
        } else {
            head = node.next;
        }
        
        if (node.next != null) {
            node.next.prev = node.prev;
        } else {
            tail = node.prev;
        }
    }
    
    private void addToTail(char c) {
        DLLNode newNode = new DLLNode(c);
        if (tail == null) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
        charToNode.put(c, newNode);
    }
    
    public void add(char ch) {
        count.put(ch, count.getOrDefault(ch, 0) + 1);
        
        if (count.get(ch) == 1) {
            // First occurrence - add to DLL
            addToTail(ch);
        } else if (count.get(ch) == 2) {
            // Second occurrence - remove from DLL
            if (charToNode.containsKey(ch) && charToNode.get(ch) != null) {
                removeNode(charToNode.get(ch));
                charToNode.put(ch, null);
            }
        }
        // If count > 2, already removed, do nothing
    }
    
    public char getFirstNonRepeating() {
        if (head == null) {
            return '#';
        }
        return head.data;
    }
    
    public static void main(String[] args) {
        FirstNonRepeatingOptimal solver = new FirstNonRepeatingOptimal();
        String input = "aabcbdd";
        
        System.out.println("Stream processing:");
        for (char c : input.toCharArray()) {
            solver.add(c);
            System.out.println("After '" + c + "': First non-repeating = " 
                             + solver.getFirstNonRepeating());
        }
    }
}

Complexity Analysis

  • Time Complexity: O(1) per add and O(1) per query, O(n) total
  • Space Complexity: O(1) for 26 lowercase letters (or O(k) for k unique characters)

Alternative: Using Queue

Comparison

| Approach | Add Time | Query Time | Space | |----------|----------|------------|-------| | Brute Force | O(1) | O(n) | O(n) | | DLL + HashMap | O(1) | O(1) | O(k) | | Queue + HashMap | O(1) amortized | O(1) amortized | O(n) |

Key Takeaways

  1. DLL for Order: Doubly linked list maintains insertion order efficiently
  2. HashMap for Access: O(1) lookup and removal from DLL via pointers
  3. Three States: New, seen once (in DLL), repeated (removed)
  4. Stream Processing: System must handle continuous input efficiently
  5. Queue Alternative: Simpler but may have O(n) worst case cleanup
  6. Bounded Alphabet: If only lowercase letters, space is O(26) = O(1)
  7. Real-world Use: Log processing, network packet analysis
  8. Design Pattern: Combination of multiple data structures for optimal performance
Previous
Program for nth node from the end of a Linked List