First Unique Character in a String

Question

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

Solution

這次是第二次寫，花了一點時間才寫出來。方法是用一個 set 來記錄出現過的數字，然後在遍歷字串時，每次都從下個位置跑一次 indexOf，如果在 set 裡面沒出現 && s.indexOf(s.charAt(i), i+1) == -1，那就代表他是 non-repeating character。要特別注意的是 corner cases，在這個方法裡要特別判斷最後一個 char

Optimize

有兩個解法，第一個是建立一個 int[26]，遍歷兩次字串。第一次記錄出現頻率，第二次找出 first non-repeating character

public int firstUniqChar(String s) {
        int[] freq = new int[26];

        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;
    }

第二個解法是用快慢指針。概念是快指針不僅算出 char 出現的頻率，同時也能找到當前的 non-repeating character 並更新給慢指針

public int firstUniqChar(String s) {
        if(s==null || s.length()==0) return -1;
        int len = s.length();
        int slow = 0,fast = -1;
        int[] count = new int[256];
        char[] c = s.toCharArray();
        while(++fast < len){
            count[c[fast]] ++;
            while(slow<len && count[c[slow]]>1) slow++;
            if(slow ==len) return -1;
        }
        return slow;
    }