First Unique Character in a String 387

Question

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

Examples:

s = "leetcode"

return 0.

s = "loveleetcode",

return 2.

Note: You may assume the string contain only lowercase letters.

Solution

1. one pass. 利用HashMap和two pointer。fast将遇到的character记录到hashmap中，如果遇到和slow相同的，则slow向前移动同时查hashmap，直到遇到不在hashmap中或者hashmap中数为1的character时停止，所以slow总是记录当前前unique的最小index。最后如果slow大于等于s的长度，则说明unique character不存在，返回-1，否则返回slow。

2. two pass. 第一遍遍历s，利用hashmap记录所有character出现的次数，然后再遍历s，遇到在hashmap中数值为1的character则返回当前index。hashmap也可以改用array，这样可以提高性能。

代码如下：

public class Solution {
    public int firstUniqChar(String s) {
        if (s == null || s.length() == 0) {
            return -1;
        }

        // if(s.length() == 1) {
        //     return 0;
        // }

        // HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        // int slow = 0;
        // int fast = 1;
        // map.put(s.charAt(slow), 1);

        // while (fast < s.length()) {
        //     char curt = s.charAt(fast);
        //     if (map.containsKey(curt)) {
        //         map.put(curt, map.get(curt) + 1);
        //     } else {
        //         map.put(curt, 1);
        //     }

        //     if (s.charAt(slow) == curt) {
        //         while (slow < s.length() && map.containsKey(s.charAt(slow)) && (map.get(s.charAt(slow)) > 1)) {
        //             slow++;
        //         }
        //     }

        //     if (slow > fast) {
        //         fast = slow;
        //     } else {
        //         fast++;
        //     }
        // }

        // return slow < s.length()? slow : -1;

        //HashMap or Array
        // Map<Character, Integer> map = new HashMap<Character, Integer>();
        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            // map.put(c, map.containsKey(c)? map.get(c) + 1 : 1);
            freq[c-'a']++;
        }

        for (int i = 0; i < s.length(); i++) {
            // if (map.get(s.charAt(i)) == 1) {
            //     return i;
            // }
            if (freq[s.charAt(i) - 'a'] == 1) {
                return i;
            }
        }
        return -1;
    }
}