387. First Unique Character in a String

二刷 08/2022

Version #1 Array as HashMap

Time O(N)

Space O(1)

Runtime: 15 ms, faster than 69.80% of Java online submissions for First Unique Character in a String.

Memory Usage: 48.7 MB, less than 65.14% of Java online submissions for First Unique Character in a String.

class Solution {

    public int firstUniqChar(String s) {

        int[] count = new int[26];

        for (int i = 0; i < s.length(); i++) {

            count[s.charAt(i) - 'a']++;

        }

        for (int i = 0; i < s.length(); i++) {

            if (count[s.charAt(i) - 'a'] == 1) {

                return i;

            }

        }

        return -1;

    }

}

一刷

Version #3 LinkedHashMap
一个虽然效率不高但是非常厉害的解法
通过visited来记录是不是visit过
通过map来保持只被visit过一次的char，及其对应的index
用LinkedHashMap来保证取到的第一个就是第一个index
如果不用LinkedHashMap也可以把整个map.values() iterate一遍取min
39.40 %
class Solution {
    public int firstUniqChar(String s) {
        if (s == null || s.length() == 0) {
            return -1;
        }
        // key->char, value->index
        Map<Character, Integer> map = new LinkedHashMap<>();
        Set<Character> visited = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            if (!visited.contains(s.charAt(i))) {
                map.put(s.charAt(i), i);
                visited.add(s.charAt(i));
            } else {
                map.remove(s.charAt(i));
            }
        }
        if (map.size() > 0) {
            return map.entrySet().iterator().next().getValue();
        }
        return -1;
    }
}


Version #2 HashMap

10.08 %
class Solution {
    public int firstUniqChar(String s) {
        if (s == null || s.length() == 0) {
            return -1;
        }
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), 1 + map.getOrDefault(s.charAt(i), 0));
        }
        for (int i = 0; i < s.length(); i++) {
            if (map.get(s.charAt(i)) == 1) {
                return i;
            }
        }
        return -1;
    }
}

Version #1 Array of Count
Two pass method with integer array

54.02%
public class Solution {
    public int firstUniqChar(String s) {
        if (s.length() == 0) return -1;
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
        }
        for (int j = 0; j < s.length(); j++) {
            if (count[s.charAt(j) - 'a'] == 1) return j;
        }
        return -1;
    }
}