Cracking the Code Interview 1-2 Check Permutations (JavaScript)

Today I will go over the Cracking the Code Interview 1-2 Check Permutations.

Per the problem statement

Given two strings, write a method to decide if one is a permutation of the other.

As always lets think this through starting with a naive implementation.

Implementation 1. Sort the strings

There is a pretty "quick and dirty" way to approach this problem. One could simply sort both strings. Once sorted then we simply have to do a string comparison of the two to determine whether they are permutations of one another. A quick implementation might look like

const str1 = abba;
const str2 = baab;

//we need to make the strings arrays first, sort, then concatenate back into strings
const sortedStr1 = str1.split("").sort().join("");
const sortedStr2 = str2.split("").sort().join("");

//return whether they are equal now
return sortedStr1 === sortedStr2;

This is probably what I would do in my head if I was trying to check if two string are permutations of one another. But as it turns out this is quite expensive.

Complexity analysis

Right away it should be concerning we are sorting 2 arrays of arbitrary length. Remember any time we have to iterate through an array all the way its an automatic O(n). In this case if we drop the lower terms we end up with O(str1.length*str2.length). We will make this better in the second implementation by adding a length check base case. But really at the end of the day we are looking at always doing O(n^2) since both strings are equal length.

Approach 2. Hash table

I hate to be boring but in this case our old friend hash table is the solution. It actually does not improve the worst case runtime. But the average time can improve quite a bit. Without to much further ado let's look at an implementation:

const checkPermutations = (stra: string, strb: string) => {
  //base case
  if (stra.length !== strb.length) return false;

  const hashTable: Record<string, number> = {};

  //fill up hash table w/ stra vals
  for (let i = 0; i < stra.length; i++) {
    hashTable[stra[i]] ? (hashTable[stra[i]] = 1) : hashTable[stra[i]]++;
  }

  //now audit hash table against strb
  for (let i = 0; i < strb.length; i++) {
    if (hashTable[strb[i]]) {
      hashTable[strb[i]]--;
    } else {
      return false;
    }
  }

  return true;
};

Okay lets talk through some things first. First off we can make a pretty immediate base case assumption that if the strings arent equal they can't be permutations of each other. Well worth checking. With that out of the way we then initialize our hash table.

First step is to fill our hash table (or dictionary) with the values from the first string. But what we are storing is instead keys that represent a character and the corresponding "count" of that letter found in the string. So for example:

const str = hello;

//resulting hash table
const hashTable = {
  h: 1,
  e: 1,
  l: 2,
  o: 1,
};

This is important because this will serve as our lookup table in the second loop.

In loop two we will then loop through each character in the second string and look at the hash table. If the value exists in the hash table with a value great than 1 we decrement the value associated with that key and then keep looping.

If at any time we cant find the character from string b in the hash table or we find it and our count for that key is zero we immediately exit out. We do so because that means either this character does not exist in the other string or there are more instances of this character in the first string than the second. Which would mean of course they are not permutations of each other!

Complexity analysis

So the worst case scenario is still unfortunately O(n^2). And that kind of makes sense. You simply cannot know whether two strings are permutations of each other without checking each character at least once. So intuitively this is our best case scenario. However what we have done is given ourselves an escape hatch of sorts. As soon as we find a mismatch between character count or the character does not exist in one of the strings we can immediately exit out. So our average case has the potential to drop significantly.

Thank you as always for reading and best of luck in your journey of learning algorithms!