Finding duplicate characters in a string in javascript

A very common programming interview question is that given a string you need to find out the duplicate characters in the string.

A string is just an array of characters so undoubtedly we will think of solving the problem using array operations. A for loop will loop through the list of characters and we will compare each character to see if it has duplicate in the rest of the characters. Hence we will need to do another loop over the rest of the characters… “But wait”, you might say, “This is slow and no real programmer will do this.” You are not content with the O(n²) solution because you are a real programmer. Let’s use a Hashmap to store the result. It would look something like this in ES 6.

const str = "afewreociwddwjej";
function findRepeat(str) {
  const arr = str.split('');
  const hash = new Map();
  const result = [];
  // If repeat the value is false, if no repeat the value is true
  for (let i = 0; i < arr.length; i++) {
    if (hash.get(arr[i]) === undefined) {
      hash.set(arr[i], true);
    } else {
      const value = hash.get(arr[i]);
      if (value) {
        hash.set(arr[i], !value);
      }
    }
  }
  hash.forEach((v, k) => {
    if (!v)
      result.push(k);
  });
  return result;
}
console.log(...findRepeat(str));

This is just an example of what it might look like using a hash. There are many variants of this method but as long as you use hash that will do.

Here the hash is a Map object and it will store each character that is available in the string as key. Initial value of any key in the map is undefined. If the character is repeated we mark it as false if no repeat we will mark it as true . Once we have this data structure it is very easy to find out which characters are repeated. Now it takes O(n) to solve the problem.

All good now. But what if you don’t want to use a Hashmap? “It looks cumbersome and a lot of codes!”, you may argue. OK, again, as a real programmer we want to write as little code as possible so we can have time to do more interesting stuff. Do we have other options?

Turns out we do have another option. The javascript regular expression is here for a rescue. Here is another solution using regular expression:

function howManyRepeated(str){
  const result = [];
  const strArr = str.toLowerCase().split("").sort().join("").match(/(.)\1+/g);
  
  if (strArr != null) {
    strArr.forEach((elem) => {
      result.push(elem[0]);
    });
  }
  return result;
}
console.log(...howManyRepeated(str));

What the hell is that? At first glance it may not make much sense. Just one line of code is enough to get the repeated characters. Awesome, right? But what is going on?

It goes like this. We first turn the string into a character array and then sort the array and put them together to form a new string. This string is sorted so we can use a regular expression to match the repeated characters. A repeated character is matched by /(.)\1+/ , which essentially means to grab the capturing group and check if the following text is the same text as most recently matched by the 1st capturing group. The strArr stores the matched groups of characters so each of its element contains more than 1 character. It’s a very neat solution I find on Stackoverflow.com. I feel it is best to share with you.