char[ ] map, int[ ] map

• 并不是所有时候都需要开一个HashMap

• 如果只是为了纪录key-> count并且key服从某种均匀分布的规律（i = 1 ~ N, key is a alpha character which means from 'a' to 'z'）

• 可以建立array of map,会快很多

First Unique Character in a String

• 这题分别针对Extra space和No space共想出5种方法

• Extra space---O(N)

  • char[ ] map = new char[26] (Make sure only has alpha character, otherwise has to allocate new char[256])

  • hashmap

  • linkedhashmap

• No extar space---O(N^2)

  • java api--- s.indexOf(i) == s.lastIndexOf(i)

  • two pointer

• Naive的想法当然是从O(N^2)到O(N)

• 不过鉴于题目本身比较简单，可以直接问面试官是否可以用Extra space,然后建char[] map

public int firstUniqChar(String s) {
        int freq [] = new int[256];
        for(int i = 0; i < s.length(); i ++)
            freq [s.charAt(i) - 'a'] ++;
        for(int i = 0; i < s.length(); i ++)
            if(freq [s.charAt(i) - 'a'] == 1)
                return i;
        return -1;
    }

public int firstUniqChar(String s) {
        if(s == null || s.length() < 1) return -1;
        if(s.length() == 1) return 0;
        int len = s.length();
        int[] count = new int[256];
        int slow = 0;//slow means the first unqie char
        int fast = 1;//means the iter pointer which starts from the next of slow
        count[s.charAt(slow)]++;

        while(fast < len){
            count[s.charAt(fast)]++;

            while(slow < len && count[s.charAt(slow)] > 1){
                slow++;//find the first unqiue char
            }
            if(slow >= len){
                return -1;//no unique char
            }
            if(count[s.charAt(slow)] == 0){//not yet visited before
                count[s.charAt(slow)]++;
                fast = slow;
            }
            fast++;
        }
        return slow;
    }