Beginner LevelData Structures & Algorithms
How do you find the first non-repeating character in a string?
ā Interview Prompt: Find the first non-repeating character in O(N) time using a frequency array or hash map.
Two-Pass Approach: $O(N)$ time, $O(1)$ space (26 characters max):
1
First pass: Count frequency of every character.
2
Second pass: Return the first character with frequency = 1.
Alternatively, use a LinkedHashMap to maintain insertion order while tracking frequencies (required if you need the actual character, not just its index).
Code Implementation Example
typescript
function firstUniqChar(s: string): number {
const freq = new Array(26).fill(0);
const a = 'a'.charCodeAt(0);
// Pass 1 ā count frequencies
for (const c of s) freq[c.charCodeAt(0) - a]++;
// Pass 2 ā find first unique
for (let i = 0; i < s.length; i++) {
if (freq[s.charCodeAt(i) - a] === 1) return i;
}
return -1;
}
console.log(firstUniqChar("leetcode")); // 0 ('l')
console.log(firstUniqChar("aabb")); // -1š”Two-pass O(N) first unique character using a 26-slot frequency array.
šÆ Interview Key Takeaway
A fixed-size frequency array (26 for lowercase letters) gives O(1) space vs O(N) for a HashMap. Always clarify the character set.
#DSA#Strings#Hash Map#Frequency Count#Beginner
Back to all Data Structures & Algorithms Questionsā