Leetcode 242. Valid Anagram: An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

1. Introduction

Given two Strings, s and t, return true if t is an anagram of s, and false otherwise. 

Example 1:

Input: s = “anagram”, t = “nagaram”

Output: true

Example 2:

Input: s = “dictionary”, t = “indicatory”

Output: false

2. Content

Both the input Strings, s and t must have the same characters with the same frequency. 

For input, s = “anagram”, t = “nagaram”, the output should be true because every character that occurs in String s occurs in t with the same frequency.

I will show you 3 different ways to solve this problem, along with their time and space complexity.

3. Using Sorting

One simple way to solve this question is to sort both the inputs and check if they are equal or not. We cannot just sort the String input as Strings are immutable in Java. So we can get the char array(toCharArray()) from String and then sort it. Then to check equality of two arrays we use java.util.Arrays.equals method.

Below is the code:

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    char[] sArr = s.toCharArray();
    char[] tArr = t.toCharArray();
    Arrays.sort(sArr);
    Arrays.sort(tArr);
    return Arrays.equals(sArr, tArr);
}

Time Complexity: 

1. Sorting takes O(n log n) where n is the length of String s or String t. We are restricting our code to run only if both input’s length are the same. 
2. Array.equals takes O(n) time.
3. As the sorting time dominates the equality time, the final time complexity is O(n log n).

Space Complexity:

1. Depending on the Sorting algorithm used by the programming language, it can take additional space.
2. toCharArray() method takes O(n) space in Java. 
3. As we have language and internal implementation dependent information, we can say that space complexity is O(1). But mention the above information, as it can vary based on language and internal implementation.

4. Using counter[] array

Now let us solve this question using the counter. We can increase the count by one of the characters for input String s. Then for input String t we will decrease the counter by one. If the counter for character in String t is less than 0 then we found the character that doesn’t exist in input String s but exists in input String t. So we can return false. If we don’t encounter any such characters, then we return true.

Below is the code:

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
        
    int[] ch = new int[256];
        
    for(int i = 0; i < s.length(); i++) {
        ch[s.charAt(i)]++;
    }

    for(int i = 0; i < t.length(); i++) {
        ch[t.charAt(i)]--;
        if(ch[t.charAt(i)] < 0) {
            return false;
        }
    }

    return true;

}

Time Complexity:

1. O(n) where n is the length of input String s or String t. 

Space Complexity:

1. O(1) as the size of the counter array doesn’t change based on input size. It is a constant size array.

5. Using HashMap

We can solve this problem using HashMap too. Instead of using a counter[] array, we can do the same with HashMap.

Below is the code:

public boolean isAnagram(String s, String t) {
    if(s.length() != t.length()) {
        return false;
    }
    Map<Character,Integer> sMap = new HashMap<>();
        
    for(int i = 0; i < s.length(); i++) {
        sMap.put(s.charAt(i), sMap.getOrDefault(s.charAt(i), 0) + 1);
        sMap.put(t.charAt(i), sMap.getOrDefault(t.charAt(i), 0) - 1);
    }
        
    for(char c : sMap.keySet()) {
        if(sMap.get(c) != 0) {
            return false;    
        }
    }
        
    return true;
}

Time Complexity:

1. O(n) where n is the length of input String s or String t.

Space Complexity:

1. O(n) where n is the length of input String s or String t.

6. Conclusion:

In this article, we saw how to check if two Strings are anagram using 3 different methods.