firstDuplicate. Given a string which might have duplicate letters, write a function to find the first duplicate.

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.