387. First Unique Character in a String

Problem

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.

Problem Summary

Given a string, find its first non-repeating character and return its index. If it does not exist, return -1.

Solution Approach

An easy problem, requiring outputting the first character that is not repeated.
The idea in solution two only beats 81% of users, but if in the test cases the string s is very long and the characters that satisfy the condition are all in later positions, this idea should have more advantages. Record the first occurrence position and the last occurrence position of each character. Traverse s once the first time. The second time, only traversing the array is enough.

Code


package leetcode

// Solution One
func firstUniqChar(s string) int {
	result := make([]int, 26)
	for i := 0; i < len(s); i++ {
		result[s[i]-'a']++
	}
	for i := 0; i < len(s); i++ {
		if result[s[i]-'a'] == 1 {
			return i
		}
	}
	return -1
}

// Solution Two
// Runtime: 8 ms
// Memory Usage: 5.2 MB
func firstUniqChar1(s string) int {
	charMap := make([][2]int, 26)
	for i := 0; i < 26; i++ {
		charMap[i][0] = -1
		charMap[i][1] = -1
	}
	for i := 0; i < len(s); i++ {
		if charMap[s[i]-'a'][0] == -1 {
			charMap[s[i]-'a'][0] = i
		} else { // Already appeared
			charMap[s[i]-'a'][1] = i
		}
	}
	res := len(s)
	for i := 0; i < 26; i++ {
		// Appeared only once
		if charMap[i][0] >= 0 && charMap[i][1] == -1 {
			if charMap[i][0] < res {
				res = charMap[i][0]
			}
		}
	}
	if res == len(s) {
		return -1
	}
	return res
}