Valid Anagram

Difficulty: Medium

Asked in: Google, Amazon, Microsoft

Understanding The Problem

Problem Description

Given two strings s and t, Write a program to check whether the two strings are an anagram of each other or not.

Problem Note:

• s is an anagram of t if the characters of s can be rearranged to form t.
• You may assume the string contains only lowercase alphabets.

Example 1

Input: s = “afteracademy” , t = “academyafter”
Output: 1

Example 2

Input: s = “mindorks”, t = “mindrocks”
Output: 0

Solutions

We will be discussing two solutions for this interview problem

1. Using Sorting Technique: Sort the characters in both of the strings and compare them one by one.
2. Using Hashing: Create a hashmap of the number of occurrences of each character in the first string and match the second string with it.

You may try this problem here

1. Using Sorting Technique

If you rearrange the letters of s into t, then that would be anagram to each other. If we could sort both the strings, we will have the characters organized in an order which will be identical if both the strings are anagram to each other. So, strings with different lengths would never be an anagram.

Solution steps

1. If the length of both the strings are different, then return 0, else step 2
2. Sort both the strings s and t
3. Compare their characters one by one

• If any of the character mismatches, return 0
• If all the characters are identical in both the strings, return 1

Pseudo Code

bool isAnagram(String s, String t) {
    if (not s.length() == t.length()) {
        return 0
    }
    char[] str1 = s.toCharArray()
    char[] str2 = t.toCharArray()
    sort(str1)
    sort(str2)
    for(i = 0 to i < s.length()){
        if(str1[i] != str2[i]){
            return 0
        }
    }
    return 1
}

Complexity Analysis

Time Complexity: O(n log n)

Space Complexity: O(n)

Note: In most of the programming language, strings are immutable and thus requires conversion into character array to manipulate it.

Critical Ideas to Think

• What is an anagram?
• Why did sorting work?
• Do you feel that we sorted just because we can match the number of occurrences of each character? If yes, then can you optimize the time complexity?

2. Using Hashing

When we sorted the strings and started matching in the previous approach, we were only checking their occurrences of each character by grouping them together.

So, we could do that by storing the number of occurrences of each character in an array where each index represents the ASCII of the respective character. In this way, we don’t have to reorder the strings, we could directly increment the value at the index by one on each occurrence and compare the second string with it. Instead of using an array whose each index represent the ASCII of character, we could also use a hashmap, whose key is the character itself and the value is their number of occurrence in the first string which works exactly the same as of array.

Solution Steps

1. Return 0 if the length of the strings are unequal else step 2
2. Create a counter array of size depending on the possible number of different characters and initialize it with 0
3. For each character of s increment the counter[i] (where i is the ASCII of the character) and for each character of t decrement the counter[i]
4. If all the index of counter contains 0 in the end, return 1 else return 0

Pseudo Code

bool isAnagram(String s, String t) {
    if (not s.length() == t.length()) {
        return 0
    }
    // assuming the characters of the strings be lower case only
    int counter[26]
    for (int i = 0 to i < s.length()) {
        counter[s[i] - 97] = counter[s[i] - 97] + 1
        counter[t[i] - 97] = counter[t[i] - 97] - 1
    }
    for (i=0 to i < s.length()) {
        if (counter[i] != 0) {
            return 0
        }
    }
    return 1
}

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1), The space utilized by the counter array is constant.

Critical Ideas to Think

• Why did we return false whenever counter[i] != 0 is true?
• Why did we subtract s[i] with 97?
• How is this approach better than the sorting approach?
• What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

Comparison of Solutions

Suggested Problems to Solve

• Group Anagrams
• Palindrome Permutation
• Find All Anagrams in a String

If you have any more approaches or you find an error/bug in the above solutions, please comment down below.

Happy Coding! Enjoy Algorithms!