FirstUniqueCharacterInAString [source code]

public class FirstUniqueCharacterInAString {
    public int firstUniqChar(String s) {
        char[] letters = s.toCharArray();
        int[] rightmostIndices = new int[26];
        Arrays.fill(rightmostIndices, -1);
        for (int i = 0; i < letters.length; i++) {
            rightmostIndices[letters[i] - 'a'] = i;
        }
        for (int i = 0; i < letters.length; i++) {
            if (rightmostIndices[letters[i] - 'a']++ == i) return i;
        }
        return -1;
    }
}

首先相处暴力解, 这个很简单, 直接扫一遍, 没看到一个 char, 向后再来一个内循环看是否在后面的 sublist 里面就行了; 速度是O(n^2);

这个问题其实说到底好像还是一个保存历史信息类的 stream 算法应该就能解决. 这里的 hashtable 可以用 array 来实现;
这个好像连历史信息类的难度都不算, 就是一个 count 类的题目就行了;

最后问题实际上是比我想想的要复杂的, 我摸索出来的思路是, 先过一遍, 记录每一个字母的rightmost occurrence index, 然后再过一遍, 如果在i 不是letters[i]的rightmost occurrence, 那么 i 就是我们想要的结果;
但是这个算法有一个问题, 比如"ccc", 这个 case, 前两个 c 随你不会触发premature return的, 但是最后一个 c, 也就是实际上的 rightmost occurrence, 却会触发premature return. 这个不是我们想要的.
实际上解决的办法非常简单, 就是在第二个循环里面, 如果 premature return 失败了, 我们就知道letters[i]一定有重复, 那么我们只要保证 rightmost 的那个 c 也不能触发rightmostIndices[letters[i] - 'a'] == i就行了, 所以直接把这个 rightmostIndices 给++, 这样 rightmost 也会失败.
实际写的时候可以写的更简单一些, 因为只要进入了第二个循环, 我们就要++, 所以干脆直接写在 header 里面; 就算是 if 成功了, 这个时候也已经 return 了, 多出来的一个++无所谓;

速度是18ms, 93%, 还算不错;

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