Cracking The Coding Interview Together – Problem 1.2: Check Permutation?

Welcome back again to Cracking The Coding Interview Together series. Last time we looked at the first problem and defined a format on how to tackle programming interview question in detail. I will be using the same format throughout the series and if you haven't read that article, please go ahead and read.

Cracking the Coding Interview Together – Problem 1: Is Unique?

Exploring the “Is Unique” problem from Cracking the Coding Interview, step by step — just like in a real interview.

The Dev LearningsThe Dev Learnings Team

We will follow the format as follows

1. Understand the problem statement together
2. Ask any questions, that you would like to ask the interviewer
3. I would urge you to take your time here and try to come up with your own solution before going forward
4. Think how you would go about solving the problem(you would be talking out loud in front of the actual interviewer)
5. Write code and understand how it works and explain it to your interviewer

Problem Statement

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

Analyse Problem Statement

Let's try to analyse the problem statement first. I am sure you know what strings are, we also discussed briefly in the previous post. But also let's try to understand what Permutation means. In simple terms:

A permutation means a rearrangement of elements.

For example, if you have the string "ABC", the permutations are:

ABC
ACB
BAC
BCA
CAB
CBA

Now we have all the technical terms out of the way, let's try to understand the problem. It says that given two strings we have to check if one is a permutation of other. Since permutation is a specific arrangement of characters within the string, we can establish the following:

1. Strings must be of the same size to be a permutation of each other, right!
2. For the sake of simplicity we might want to ignore the case of the letters i.e. whether they are in upper case or lower case we consider them equal.
3. Both the strings must contain the same letters with equal frequency - this is applicable for the strings containing duplicate characters. Every character in both the strings must have the same frequency

let's say if we have a String: HELLO then letter L has a frequency of 2 because it appears twice in the string. It means that its permutation must also contain letter L twice regardless of its position e.g. LEHLO is a permutation of the original string.

Example:
✅ "abc" and "bca" → permutations
❌ "abc" and "abb" → not permutations

At this point you must start thinking about any edge cases or anything else that you might want to clear with the Interviewer.

Questions for the Interviewer

I hope you are doing this exercise with me and not simply relying on me to do it. If you are simply reading it, it won't be much useful unless you put your mind to work. Last chance for you to really think about the question and see if there is something that you would like to clarify.

I hope you have come up with your own set of questions. Let me put up mine:

1. Can provided string be null? Simple case yet most of us ignore this and if you don't know NPEs i.e. Null Pointer Exceptions are the most common ones that break the code in production. Let's not make this mistake and handle this appropriately
2. What if both the strings are null, should program return true or false.
3. Is that OK, if we ignore the case of the letters? We made the assumption in previous section to ignore it, but without a confirmation from the interviewer its useless. So let's ask the interviewer.

Let's we got the following answers from the Interviewer:

1. Yes, input string can be null
2. You should return true in that case
3. Yes, you can ignore the case

Think about the Solution

Now you have a pretty good idea about the problem statement and have clarified your questions and doubts. Now is the time to take few mins to come up with a solution. You could also think out loud to let the Interviewer analyse your problem solving skills and how are you approaching and tackling the problem.

I would request you REALLY think about the solution now.

Let's consider the following to handle the obvious situations

1. We must put a null check for both the input strings and if any one of it is null, we can return false but if both are null then return true
2. We should also think of standardizing the strings either in uppercase or lowercase or we could also somehow do the comparison by ignoring the case
3. We could also return early with false, if both the strings are not equal in size. This can never happen, that a string is a permutation of the other and not have the same size.

How about the algorithm, let's also spend sometime to think about this.

We must make sure that the frequency of each character is same in both the strings and if it is then it means that the string is a permutation of the other. But if the frequency of even one of the character is not same it means they are not permutation of each other.

Option 1: Using HashMap to store the frequency

We could use hashmap to store the frequency of both the strings and then compare those hashmaps to deduce if all the characters have the same frequency or not.

Can you think of any other way to solve this problem? 🤔

Take your time...

Option 2: Using Sorting

Now, this is a big hint for you let's see if now you can come up with a solution if you couldn't already.

Anyway let me describe the approach and intuition here. So say we sort both the strings, then we could simply check if both the strings are equal or not, cool trick, right!

e.g. HELLO and LEHLO let's try to see how they would like after sorting

EHLLO and EHLLO

We simply compare both strings and voila now we can easily tell if they are permutation of each other or not.

Write Code & Explain

So now you have everything, you have understood the problem, you have clarified your doubts and now you have a good idea how you can solve the problem. Now only the easy part, write the code 😃

Solution 1: Using Hashmap

public static boolean isPermutation(String str1, String str2) {
    if(str1 == null && str2 == null) return true;
    if(str1 == null || str2 == null) return false;
    if(str1.length() != str2.length()) return false;
    // Count frequencies of all characters in str1
    for (char character : str1.toCharArray()) {
        Integer frequency = map.getOrDefault(character, 0);
        map.put(character, frequency + 1);
    }

    // Decrease count while reading str2
    for (char character : str2.toCharArray()) {
        if (map.getOrDefault(character, 0) == 0) return false;
        Integer freq = map.get(character);
        map.put(character, freq - 1);
    }
    return true;
}

You must also describe the time and space complexity of your solution.

In this case you are going through all the characters of the string twice at the max. Consider if string has n characters

Time Complexity = O(n)

Space Complexity = O(k) where k is the number of unique characters if all are unique that it would become O(n)

Solution 2: Using Sorting

boolean isPermutation(String s1, String s2) {
    if (s1.length() != s2.length()) return false;
    char[] a = s1.toCharArray();
    char[] b = s2.toCharArray();
    Arrays.sort(a);
    Arrays.sort(b);
    return Arrays.equals(a, b);
}

Time Complexity = O(nlogn) because of the sorting

Space Complexity = O(n)

Final Thoughts

I hope you are enjoying the weekly series, Cracking The Coding Interview - Together!

If you have any questions/comments please write to me, you would have to simply visit the page on browser and you should be able to do just that. I can't wait to hear from everyone of you.

Happy Coding!