Check whether two strings are anagram or not

Difficulty: Easy, Asked-in: Google, Amazon, Microsoft, Goldman Sachs.

Key takeaway: An excellent problem to learn problem-solving using direct address table. We can use similar approach to solve several other coding questions.

Let’s understand the problem

Given two strings str1 and str2 of size m and n, write a program to check whether two given strings are anagram of each other or not.

String str1 is an anagram of str2 if characters of str1 can be rearranged to form str2. In other words, an anagram of a string is another string that contains same characters in different order.
Both strings may contain duplicate characters.
Characters in both strings are lowercase English characters.

Examples

Input: str1= “dusty” , str2= “study”, Output: true

Input: str1= “state” , str2= “taste”, Output: true

Input: str1= “enjoyalgorithms”, str2= “enjoymathematics”, Output: false.

Discussed solution approaches

Brute force solution using nested loops
Using sorting and comparing characters
Counting occurrences of each character using two frequency tables
Counting occurrences of each character using one frequency table

Brute force solution using nested loops

Solution idea

One basic solution would be to pick each character from str1 and search for that character in str2. If any character is missing, both strings are not an anagram of each other. On another side, if characters are repeated, then frequency of repeated characters must be same in anagrams strings. To ensure this, we can replace the found characters in str2 with an empty flag ‘\0’.

Solution pseudocode

validAnagram(str1, m, str2, n)
    if m is not equal to n
        return false

    for i from 0 to m - 1
        pos = linearSearch(str2, n, str1[i])

        if pos equals -1
            return false
        else
            str2[pos] = '\0'

    return true

Solution analysis

We are searching each character of str1 in str2 using the linear search. So time complexity = m * O(n) = O(mn). We are using constant extra space, so space complexity = O(1).

Using sorting and comparing characters

Solution idea

Can we think of improving time complexity? One idea is to sort both strings and compare each character. This will arrange all repeated characters together and help us to compare their frequency in both strings.

Step 1: If (m != n), strings are not an anagram of each other.

Step 2: Now sort strings in increasing order. What sorting algorithm will be efficient in this scenario? Only lowercase are present in the input, so the string will contain 26 unique characters. Instead of using O(nlogn) sorting, we can use a direct address table of size 26 to count the frequency of each character and sort the string in O(n) time and O(1) space. Note: This idea is similar to counting sort.

sortString(str, n)
    create count array of size 26, initialized to 0
    for i from 0 to n - 1
        count[str[i] - 'a'] = count[str[i] - 'a'] + 1

    k = 0
    for i from 0 to 25
        repeat count[i] times
            str[k] = character 'a' + i
            k = k + 1

Step 3: Now run a loop from i = 0 to m - 1 or i = 0 to n - 1 and compare characters at index i in both strings. If we find any unequal character in the sequence, return false. Otherwise, by the end of the loop, return true.

Solution pseudocode

validAnagram(str1, m, str2, n)
    if m is not equal to n
        return false

    sortString(str1, m)
    sortString(str2, n)

    for i from 0 to m - 1
        if str1[i] is not equal to str2[i]
            return false

    return true

Solution analysis

We are sorting and comparing both strings. So the time complexity = Time complexity of sorting str1 + Time complexity of sorting str2 + Time complexity of comparing sorted strings = O(n) + O(n) + O(n) = O(n). We use constant extra space, so space complexity = O(1).

Counting characters using two direct address tables

Searching is one of the critical operations to solve this problem. So, can we think of using hash table or direct address table to compare frequency of characters? Hash table is an efficient data structure for searching, insertion and deletion in O(1) time average.

Solution idea

All are lowercase characters, which have 26 possible values. So we can create two separate direct address tables of size 26 to store frequency of each character in both strings. We can directly store values in each table using the ASCII value of characters.

After storing values in direct address tables, we traverse them linearly and compare the frequency count of each character. If values in both tables are equal, then strings are anagrams of each other.

Solution pseudocode

validAnagram(str1, m, str2, n)
    if m is not equal to n
        return false

    create freqCount1 and freqCount2 arrays of size 26, initialized to 0

    for i from 0 to n - 1
        freqCount1[str1[i] - 'a'] = freqCount1[str1[i] - 'a'] + 1
        freqCount2[str2[i] - 'a'] = freqCount2[str2[i] - 'a'] + 1

    for i from 0 to 25
        if freqCount1[i] is not equal to freqCount2[i]
            return false

    return true

Solution analysis

We are running three separate loops, where 1st and 3rd loops run constant times and the 2nd loop runs n times. So time complexity = Time complexity of initialising direct address tables + Time complexity of storing direct address tables + Time complexity of comparing direct address tables = = O(1) + O(n) + O(1) = O(n).

The size of direct address tables are constant, so space complexity = O(1) + O(1) = O(1).

Counting occurrences of characters using one direct address tables

The critical question is: Can we optimize space and solve problem using one direct address table?

Solution idea

Suppose we traverse the first string and store frequency count of each character in a direct address table of size 26. Now we need to do slight modifications to the above approach.

Instead of storing frequency count of second string in a separate table, we traverse second string and decrement frequency of each character in direct address table of first string. Now at this stage, if both strings are anagrams, then all values stored in direct address table must be 0. So we traverse the table to check this. If we find any value not equal to 0, return false. Otherwise, by the end of loop, return true.

Solution pseudocode

validAnagram(str1, m, str2, n)
    if m is not equal to n
        return false

    create freqCount array of size 26, initialized to 0

    for i from 0 to n - 1
        freqCount[str1[i] - 'a'] = freqCount[str1[i] - 'a'] + 1

    for i from 0 to n - 1
        freqCount[str2[i] - 'a'] = freqCount[str2[i] - 'a'] - 1

    for i from 0 to 25
        if freqCount[i] is not 0
            return false

    return true

Solution analysis

Time complexity = Time complexity of traversing first string and storing values in direct address table + Time complexity of traversing second string and decrementing values in direct address table + Time complexity of checking 0’s in direct address table = O(n) + O(n) + O(n) = O(n).

We only use one frequency table of constant size, so space complexity = O(1).

Critical ideas to think about!

Is there a way to optimize the 4th approach further? Can we add an extra conditional statement in the second loop to avoid going through 3rd loop every time? Or can we think of removing the 3rd loop at all?
In 4th approach, can we merge the 1st and 2nd loop operations into a single loop?
In 2nd approach, can we solve problem by sorting just one string?
How can we modify the above approaches when uppercase, empty and lowercase characters are allowed?
Can we solve this problem using some other data structures or another approach?
Why do we assign found characters with a null value in the brute force approach?

Check whether two strings are anagram of each other

Let’s understand the problem

Examples

Discussed solution approaches

Brute force solution using nested loops

Solution idea

Solution pseudocode

Solution analysis

Using sorting and comparing characters

Solution idea

Solution pseudocode

Solution analysis

Counting characters using two direct address tables

Solution idea

Solution pseudocode

Solution analysis

Counting occurrences of characters using one direct address tables

Solution idea

Solution pseudocode

Solution analysis

Critical ideas to think about!

Suggested problems to practice

More from EnjoyAlgorithms

Self-paced Courses and Blogs