Problem 2 First Non-Repeating Characters

• use case: O(1) time + first

• 关键词，first: 必须keep时序

• O(1) time: Map(Key: Character, Value: ListNode) + DLL as Queue

• 这和LRU的区别点是什么？

  • 识别那些character是non repeating，

  • 一个字母已经出现了2次vs这个字母一次都没有出现---》你怎么知道踢了vs还是放进去

Option 1: double linkedlist + map + set

API 1: new coming character:

• double linkedlist==> 最快做删除 ==> 找到自己就能找到前一个和后一个==> 添加和删除都是O(1）的时间

• Look up operation ==> Map<Character, ListNode> ==> 很快找到ListNode ==> Set<Character>==> help determine repeat

• 分析

  • case 1先确认这个字母在不在set里，如果存在，直接ignore

  • case 2如果不在set里面

    • case2.1再看map，如果这个字母不在map里面

      • 这是我们第一次遇到这个字母，update Map + DLL

    • case2.2如果这个字母在map里面

      • 说明这个字母发生了重复，remove it from Map +DLL, add it to repeating set

API 2: who is the first?

• 看看你define的DLL里哪一段是代表时间序列

// Some code

public class Solution{
    static class Node {
        Node prev;
        Node next;
        Character ch;
        Node(Character ch) {
            this.ch;
        }
    }
    private Node head;
    private Node tail;
    private Set<Character> repeated;
    private Map<Character, Node> singled;
    public Solution() {
        head =  new Node(null);
        head.prev = head.next = head;
        tail = head;
        repeated = new HashSet<>();
        singled = new HashMap<>();
    }
    public void read(char ch){
        // if the character already exists more than once ==> ignore
        if (repeated.contains(ch)) {
            return;
        }
        
        Node node = singled.get(ch);
        // if the character appears for the first time ==> add to the list and the nonrepeated 
        if (node == null) {
            node = new Node(ch);
            append(Node);
        }
        // if the character is already in the nonrepeated ==> remove it from the map and list
        // put it into the repeat set
        else {
            remove(Node);
        }
    }
    private void append(Node node){
        // append to map
        // append to the DLL
        singled.put(node.ch, node);
        tail.next = node;
        node.prev = tail
        node.next = head;
        tail = tail.next;
    }
    
    
    private void remove(Node node) {
        // remove from the map
        // add to repeat set
        // remove from DLL
        node.prev.next = node.next;
        node.next.prev = node.prev;
        if (node == tail) {
            tail = node.prev;
        }
        node.prev = node.next = null;
        singled.remove(node.ch);
        repreated.add(node.ch);
        
    }
    
    private Character firstNonRepeating() {
        if (head == tail) {
            return null;
        }
        return head.next.ch;
    }
}

Option 2: double linkedlist + map

API 1: new coming character:

• double linkedlist==> 最快做删除 ==> 找到自己就能找到前一个和后一个==> 添加和删除都是O(1）的时间

• Look up operation ==> Map<Character, ListNode> ==> 很快找到ListNode ==> Set<Character>==> help determine repeat

• 分析

  • case 1先确认这个字母在不在map里

    • 如果存在对用的是reference node 是null，直接ignore

  • case 2如果不在set里面

    • case2.1再看map，如果这个字母不在map里面

      • 这是我们第一次遇到这个字母，如果这个字母不在map里面

    • case2.2如果这个字母在map里面

      • 如果是多次出现的字母，map里存的是这个字母的marker(mark this character already repeat)

        • use Null as special value

API 2: who is the first?

• 看看你define的DLL里哪一段是代表时间序列

// Some code
public class Solution{
    static class Node {
        Node prev;
        Node next;
        Character ch;
    }
    Node(Character ch) {
        this.ch = ch;
    }
    private Node head;
    private Node tail;
    private Map<Character, Node> map;
    
    public Solution{
        head = new Node(null);
        head.prev = head.next = head;
        tail = head;
        map = new HashMap<>();
    }
    public void read(char ch) {
        // case 1
        if (!map.containsKey(ch)) {
            Node node = new Node(ch);
            append(Node);
        }
        // case 2.2
        else if (map.get(ch) != null) {
            remove(map.get(ch));
        }
        // case 2.1, 2nd timt to see ==> do nothing
    }
    private void append(Node node) {
        map.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;
        }
        node.prev = node.next = null;
        map.put(node.ch, null);
    }
    public Character firstNonRepeating() {
        if (head == tail) {
            return null;
        }
        return head.next.ch;
    }
}