## Monday, August 22, 2016

### LeetCode 387 - First Unique Character in a String

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.

def firstUniqChar(self, s): """ :type s: str :rtype: int """ d = collections.Counter(s) ans = -1 for x, c in enumerate(s): if d[c] == 1: ans = x break return ans

https://discuss.leetcode.com/topic/56055/simpe-java-solution
``````public int firstUniqChar(String s)
int[] cache = new int[26];
for (char c : s.toCharArray()) cache[c - 'a']++;
for (int i = 0; i < s.length(); i++) {
if (cache[s.charAt(i) - 'a'] == 1) return i;
}
return -1;
}``````
https://discuss.leetcode.com/topic/55890/java-o-n-easy-one-pass-solution-20ms
``````    public int firstUniqChar(String s) {
char[] schar = s.toCharArray();
int result = schar.length;
int[] seen = new int[26];
//-1 => not visited
//-2 => repeating
//>=0 => appear once, value is index
Arrays.fill(seen, -1);
for(int i = 0; i < schar.length; i++) {
int index = schar[i]-'a';
if(seen[index] == -1) seen[index] = i;
else if(seen[index] >= 0) seen[index] = -2;
}
for(int i = 0; i < 26; i++) {
if(seen[i] >= 0) result = Math.min(result, seen[i]);
}
return result == schar.length?-1:result;
}``````

X. Two pointers
https://discuss.leetcode.com/topic/55230/java-two-pointers-slow-and-fast-solution-18-ms
The idea is to use a slow pointer to point to the current unique character and a fast pointer to scan the string. The fast pointer not only just add the count of the character. Meanwhile, when fast pointer finds the identical character of the character at the current slow pointer, we move the slow pointer to the next unique character or not visited character. (20 ms)
``````    public int firstUniqChar(String s) {
if (s==null || s.length()==0) return -1;
int len = s.length();
if (len==1) return 0;
char[] cc = s.toCharArray();
int slow =0, fast=1;
int[] count = new int[256];
count[cc[slow]]++;
while (fast < len) {
count[cc[fast]]++;
// if slow pointer is not a unique character anymore, move to the next unique one
while (slow < len && count[cc[slow]] > 1) slow++;
if (slow >= len) return -1; // no unique character exist
if (count[cc[slow]]==0) { // not yet visited by the fast pointer
count[cc[slow]]++;
fast=slow; // reset the fast pointer
}
fast++;
}
return slow;
}``````

Improved version, which checks early termination when all characters from 'a'~'z' appear more than twice. (18 ms)
``````    public int firstUniqChar(String s) {
if (s==null || s.length()==0) return -1;
int len = s.length();
char[] cc = s.toCharArray();
int slow =0, fast=1;
int[] count = new int[256];
int total = 0;
count[cc[slow]]++;
while (fast < len) {
count[cc[fast]]++;
if (cc[fast] == cc[slow]) {
total++;
if (total==26) return -1;
while (slow < len && count[cc[slow]] > 1) slow++;
if (slow >= len) return -1;
}
if (count[cc[slow]]==0) count[cc[slow]]++;
if (slow > fast) fast=slow;
fast++;
}
return slow;
}``````

LinkedHashMap will not be the fastest answer for this question because the input characters are just from 'a' to 'z', but in other situations it might be faster than two pass solutions. I post this just for inspiration.
``````public int firstUniqChar(String s) {
Map<Character, Integer> map = new LinkedHashMap<>();
Set<Character> set = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
if (set.contains(s.charAt(i))) {
if (map.get(s.charAt(i)) != null) {// no need to check
map.remove(s.charAt(i));
}
} else {
map.put(s.charAt(i), i);
}
}
return map.size() == 0 ? -1 : map.entrySet().iterator().next().getValue();
}
``````