## DEV Community is a community of 872,863 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# 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 🚀

## Discussion (4) Sahil Bondre

There is an even more space cheap method.
Hint: It uses just one integer!