288 First Non-Repeating Character In Stream (Lai)

Given a stream of characters, find the first non-repeating character from stream. You need to tell the first non-repeating character in O(1) time at any moment.

Implement two methods of the class:

• read() - read one character from the stream
• firstNonRepeating() - return the first non-repoeating character from the stream at any time when calling the method, return null if there does not exist such characters

Examples:

read:

a b c a c c b

firstNonRepeating:

a a a b b b null

Solution:

public class Solution {
    private HashMap<Character, Integer> charCountMap; // To store the count of each character
    private Queue<Character> queue; // To keep the non-repeating characters in order

    public Solution() {
        this.charCountMap = new HashMap<>();
        this.queue = new LinkedList<>();
    }

    public void read(char ch) {
        // Increase the count of the character in the hash map
        charCountMap.put(ch, charCountMap.getOrDefault(ch, 0) + 1);

        // If it's the first time this character is read, add it to the queue
        if (charCountMap.get(ch) == 1) {
            queue.offer(ch);
        }

        // Clean up the front of the queue until we have a non-repeating character at the front
        while (!queue.isEmpty() && charCountMap.get(queue.peek()) > 1) {
            queue.poll();
        }
    }

    public Character firstNonRepeating() {
        // Return the front of the queue if it's not empty; otherwise, return null
        if (queue.isEmpty()){
            return null;
            }else{
            return queue.peek();
            }
    }
}

public class Solution {
  static class Node{
    Node next;
    Node prev;

    Character ch;

    Node(Character ch){
      this.ch = ch;
    }
  }

  private HashMap<Character, Node> singled;
  private HashSet<Character> repeated;
  private Node head;
  private Node tail;
  public Solution() {
    // Initialize the class.
    tail = new Node(null);
    head = new Node(null);
    head = tail;

    singled = new HashMap<Character, Node>();
    repeated = new HashSet<Character>();
  }

  public void read(char ch) {
    // Implement this method here.
    if (repeated.contains(ch)){
      return;
    }

    Node node = singled.get(ch);
    if (node == null){
      node = new Node(ch);
      append(node);
    }else{
      remove(node);
    }
  }

  private void append(Node node){
    singled.put(node.ch, node);
    tail.next = node;
    node.prev = tail;
    node.next = head;
    tail = tail.next;
  }

  private void remove(Node node){
    node.prev.next = node.next;
    node.next.prev = node.prev;

    if (node == tail){
      tail = node.prev;
    }

    repeated.add(node.ch);
    singled.remove(node.ch);
  }

  public Character firstNonRepeating() {
    // Implement this method here.
    if (head == tail){
      return null;
    }
    return head.next.ch;
  }
}

public class Solution {
  // each node is a double linked list node
  // and it contains one distinct character.

  static class Node{
    Node prev;
    Node next;
    Character ch;

    Node(Character ch){
      this.ch = ch;
    }
  }

  // record the head and tail of the list all the time.
  // only the characters appearing just once will be
  // in the double linked list.
  private Node head;
  private Node tail;

  // for any character, it could be in three state:
  // 1. not existed yet, it will not be singled Map
  // or repeated Set.
  // 2. only existes onece, it will be in singled Map
  // and there will be a corresponding node in the list.
  // 3. exists more than once, it will be in the repeated Set.
  // and it will be removed from the list

  private HashMap<Character, Node> singled;
  private HashSet<Character> repeated;
  public Solution() {
    // Initialize the class.
    // an example of using sentinel node to eliminate some corner cases.
    tail = new Node(null);
    tail.next = tail.prev = tail;
    head = tail;
    singled = new HashMap<Character, Node>();
    repeated = new HashSet<Character>();

  }

  public void read(char ch) {
    // Implement this method here.
    // if the character already exists more than once,
    // we just ignore.
    if (repeated.contains(ch)){
      return;
    }
    Node node = singled.get(ch);
    if (node == null){
      // if the character appears for the first time,
      // it should be added to the list and added to 
      // the nonRepeated.
      node = new Node(ch);
      append(node);
    } else{
      // if the character is already in the nonRepeated
      // Map, we should remove it from the Map and list,
      remove(node);
    }
  }

  private void append(Node node){
    singled.put(node.ch, node);
    tail.next = node;
    node.prev = tail;
    node.next = head;
    tail = tail.next;
  }

  private void remove(Node node){
    // use sentinel node so that some of the 
    // corner cases will be eliminated.
    node.prev.next = node.next;
    node.next.prev = node.prev;
    if (node == tail){
      tail = node.prev;
    }
    node.prev = node.next = null;
    repeated.add(node.ch);
    singled.remove(node.ch);
  }

  public Character firstNonRepeating(){
    // when head == tail, it means there is only
    // the sentinel ndoe in the list
    if (head == tail){
      return null;
    }
    return head.next.ch;
  }
}