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.
char firstUniqChar(string s) {
int charCount[26] = {
0}
;
for (char c : s) {
charCount[c - 'a']++;
}
for (char c : s) {
if (charCount[c - 'a'] == 1) {
return c;
}
}
return ' ';Follow-up:
How would you optimize the solution if the string is too large to fit into memory?
