FirstUniqueCharacterInAStringOPT [source code]

public class FirstUniqueCharacterInAStringOPT {
    public int firstUniqChar(String s) {
        int retIndex = Integer.MAX_VALUE;
        int pos;
        for (int i = 97; i < 123; i++) {
            pos = s.indexOf(i);
            if (pos != -1 && pos == s.lastIndexOf(i)) {
                retIndex = pos < retIndex ? pos : retIndex;
            }
        }
        if (retIndex != Integer.MAX_VALUE) return retIndex;
        return -1;    
    }
}

这个是 submission 最优解, 13ms, 99%;

实际的思路实际上是类似的, 也是依靠rightmost occurrence (or later occurrrence)来帮助判断 duplicate. 他使用了一些我不太熟悉的API, 导致最后算法能够加速;

这个是 discussion 最优解:

public class Solution {  
    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;  
    }  
}

这个问题其实就是用最简单的 count 就能够解决了. 我自己的 ver1还是想的太复杂了, 不过对于思维的锻炼还是有好处的;

Problem Description

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.

Difficulty:Easy
Category:Algorithms
Acceptance:46.38%
Contributor: LeetCode
Companies
amazon bloomberg microsoft