Stream of Characters
Given a string of characters, implement a function that can process the string one character at a time, and return the first unique character in the stream. If no unique character is found, return -1.
Constraints:
- 1 <= length of string <= 10^5
- The string only contains lowercase English letters.
Examples:
Input: loveleetcode
Output: l
Explanation: The first unique character in the string is 'l'.
Solutions
Hash Map
Time: O(n)Space: O(n)
We use a hash map to count the frequency of each character in the string. Then we iterate through the string again to find the first character with a count of 1.
def firstUniqChar(s):
char_count = {}
for char in s:
if char in char_count:
char_count[char] += 1
else:
char_count[char] = 1
for char in s:
if char_count[char] == 1:
return char
return -1Follow-up:
How would you optimize the solution if the string is too large to fit into memory?
