This problem was asked by SAP Labs.
Given a string of characters, return the index of the first non-repeating character.
Example
function nonRepeatingFirstCharacter(str) {
}
const str = "abcdcaf";
console.log(nonRepeatingFirstCharacter(str)); // 1
Explanation: The non-duplicate characters in the above string are b, d and f. Since b occurs first, the index of b, which is 1 is returned.
Solution
function nonRepeatingFirstCharacter(str) {
const map = new Map();
for (const char of str) {
map.set(char, (map.get(char) || 0) + 1);
}
for (let i = 0; i < str.length; i++) {
const char = str[i];
if (map.get(char) === 1) return i;
}
return -1;
}
const str = "abcdcaf";
console.log(nonRepeatingFirstCharacter(str)); // 1
Explanation:
- Use a hash table (object) to store count of each character in one pass
- Increment count if character is already in table, default to 1
- Then loop through string again checking if char count is 1
- Return index immediately if non-duplicate char found
Top comments (0)