DEV Community

Cover image for firstDuplicate. Given a string which might have duplicate letters, write a function to find the first duplicate.
chandra penugonda
chandra penugonda

Posted on • Updated on

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
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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)