Good morning! Here's your coding interview problem for today.
This problem was asked by Apple.
Given a string which might have duplicate letters, write a function to find the first duplicate.
Example
function firstDuplicate(str) {
}
console.log(firstDuplicate('abca')) // 'a'
console.log(firstDuplicate('abcdefe')) // 'e'
console.log(firstDuplicate('abcdef')) // null
Notes: What is the time & space cost of your approach ?
Solution
function firstDuplicate(str) {
let chars = {};
for (let char of str) {
if (chars[char]) {
return char;
}
chars[char] = true;
}
return null;
}
Explanation
- Use an object (chars) to keep track of characters we've seen
- Loop through each character in the input string
- If we've seen the character before (exists in chars), return immediately
- Otherwise, add the character to chars as a key
- Return null if no duplicate is found
This runs in O(n) time and O(n) space. By short-circuiting and returning when we find the first duplicate, we avoid looping through the entire input when not needed.
Top comments (0)