LeetCode #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.
Solution
Scan the string once and use a hash map to store counts of each letter. Then find the first letter whose counts is equal to 1.
Complexity
It takes O(n) time to scan counts of each letter and O(n) time to find the first letter whose count is 1, where n denotes to counts of characters in this string. Thus, it’s time complexity is O(n).
It’s trivial that it takes O(n) extra space for the hash map.
