Algorithm practice: Find repeating characters in a string

23 Sep 2019 - John

For today’s excercise, we are given as string and our job is to find out whatever characters have a duplicate.

Step 0: break it into manageable chunks

As always, we need to be able to walk through the steps we’re about to take in plain English:

• We need to turn the string into an array of its characters.
• Then we need to build a map of key value pairs where each key is a character of our original string and their value is true if it already exists, or false if it’s unique.
• Then we need to go through this map and fill an array only with the keys whose values were true.
• Then we return the result.

Step 1: our skeleton function

We’re going to write an empty function with all the variables we need:

const str = 'afewreociwddwjej';
findRepeat = (string) => {
  const result = [];
  const arr = string.split('');
  const charMap = new Map();

  return result;
}
const dupeChars = findRepeat(str);
console.log('Duplicate characters', dupeChars);

Pretty simple stuff. We’re starting with a string of random characters that we’re going to use to test our function. Then we’re going to start a new function called findRepeat that will take care of the geavy lifting. Inside our function, we’re going to initialize three more variables:
An empty result array that we’re going to use to store our duplicate characters
An arr array containing our initial characters.
A charMap map that we’re going to use with boolean values (true/false) to determine if a character is repeated.

Step 2: it’s a map!

Let’s pice things up and use an ES6 style for loop instead of a traditional one. Because initializing counters, and adding to them on each iteration is so ES5, let’s take advantage of a new way we can do it thanks to ES6:
If we were to use a traditional for loop in our function, we would do something like this:

for( i = 0; i < arr.length; i++ ) {
  // Do stuff
}

However, we don’t need to do this. Instead, we can use the for … of syntax and declare our variables right away. So if we have an array of fruits and were to call a for on it, it would be something like this:

const fruits = ['oranges', 'apples', 'kiwis', 'bananas'];
for(const [index, value] of fruits.entries()) {
  console.log(index, value);
}

If we run this in our console, we get both the indices and values of the element in the current iteration of the loop:

0 oranges
1 apples
2 kiwis
3 bananas

So just by calling index or value we can get access to them instead of doing stuff like arr[i]. How sweet is that? Of course, you can call index and value whatever you want. I just call them index and value for clarity’s sake.
Ok, so back to our function, we’re going to use our new superpowers to go through our array and fill the map:

for (const [index, value] of arr.entries()) {
  if (charMap.get(value) === undefined) {
    charMap.set(value, false)
  } else {
    const character = charMap.get(value)
    if (!character) {
      charMap.set(value, true)
    }
  }
}

So at the beginning of our loop, we have an if block. If our map does not have a value that is equal to the current character, add a new key/value pair to our map with our character and a value of false. Then if it has a value, we set it to false. If we were to console.log the current state of the map given our initial string, we would get something like this:

Map {
  'a' => false,
  'f' => false,
  'e' => true,
  'w' => true,
  'r' => false,
  'o' => false,
  'c' => false,
  'i' => false,
  'd' => true,
  'j' => true
}

Sweet! Now we have a map we can use to weed out the falsies and return the truthies. Let’s do that!

Step 3: nothing but the truth

We’re almost there! All we need to do now is check for the values in our keys. If they’re true, send the key to our result array:

charMap.forEach((key, value) => {
  if (value) { result.push(key) }
});

Step 4: all about the results!

And that’s it! All we need to do now is print our result array to see what was duplicated:

[ 'e', 'w', 'd', 'j' ]

The complete code

const str = 'afewreociwddwjej';
findRepeat = (string) => {
  const result = [];
  const arr = string.split('');
  const charMap = new Map();
  for (const [index, value] of arr.entries()) {
    if (charMap.get(value) === undefined) {
      charMap.set(value, false)
    } else {
      const character = charMap.get(value)
      if (!character) {
        charMap.set(value, true)
      }
    }
  }
  charMap.forEach((value, key) => {
    if (value) { result.push(key) }
  });
  return result;
}
const dupeChars = findRepeat(str);
console.log('Duplicate characters', dupeChars);