Interview Prep #2: Are Strings Permutations of Each Other

Problem

We are given two strings and we are to decide whether one of the string is a permutation of the other.

Example

input: coffee fefeoc
output: true

input: day dea
output: false

Solution

On top of my mind the first thing that comes is to sort both the strings and then check if they are equal. Sorting of the strings will take O(nlogn) time and then comparing them will take O(n) time. Thus the total time complexity will be and O(nlogn).

bool compare_strings_slow(string a, string b) {
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  return a == b;
}

The bottleneck of the current approach is the sorting part which takes O(nlogn) time. Let's think of what does it mean that two strings are permutations of each other. It means that both the strings have same characters the same number of times. So we need to store all the characters and their count of both the strings. For doing this we can use hash maps.

We will iterate over the strings and store the number of times each character appears in a map. Then we can check hash maps of both of these strings and if both are equal then this means that the strings are indeed the permutations of each other. In this approach we iterate over each of the strings once and then we iterate over the hash maps for comparison. This makes the total time complexity of this approach linear that is O(n), where n is the length of strings.

An additional optimization we can add is to check if the string lengths are equal before making the maps.

bool compare_strings(string a, string b) {
  if (a.length() != b.length()) {
    return false;
  }
  map<char, int> map_a, map_b;
  // fill a map
  for (auto c : a) {
    if (map_a.find(c) == map_a.end()) {
      // character inserted for the first time
      map_a.insert({c, 1});
    } else {
      ++map_a[c];
    }
  }
  // fill b map
  for (auto c : b) {
    if (map_a.find(c) == map_b.end()) {
      // character inserted for the first time
      map_b.insert({c, 1});
    } else {
      ++map_b[c];
    }
  }

  return map_a == map_b;
}

Additionally, can you find a way to minimize the space usage of hash maps? Is there a simpler data structure for this purpose?

References: Cracking the Coding Interview - Gayle Laakmann McDowell
Have a productive day 🚀