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.
function firstUniqChar(s) {
const charCount = {
}
;
for (let i = 0;
i < s.length;
i++) {
if (charCount[s[i]]) {
charCount[s[i]]++;
}
else {
charCount[s[i]] = 1;
}
}
for (let i = 0;
i < s.length;
i++) {
if (charCount[s[i]] === 1) {
return s[i];
}
}
return -1;Follow-up:
How would you optimize the solution if the string is too large to fit into memory?
