Leetcode Daily Problem - 242. Valid Anagram

Problem Statement

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

What does this anagram mean?

• Anagram is a term defined for two strings. A string s is called an anagram of another string t if after rearranging all the letters of string s, string t can be formed.
• If s is an anagram of t that means t is also an anagram of s.

For example-

• If s = "abcd" and t = "dcab" then s and t both are anagrams of each other.
• How?
  • If we swap 'c' and 'd' in string s it becomes: "abdc"
  • Now swap "ab" with "dc", s becomes : " dcab which is string t.

Solving the problem

We're given an isAnagram function that has two strings provided and we have to return whether both are anagrams of each other or not

bool isAnagram(string s, string t) {

}

Approach

Approach -1 [O(n*n!)]
As I mentioned earlier a string s is an anagram of string t if we can get string t by rearranging letters of string s.

So, the first approach can check all the permutations of string s and if any permutation matches with string t then return true otherwise return false.

bool checkPermutation(string s, string permutation, string t)
{
    if(s.length() == 0)
    {
        return t==permutation;
    }
    for(int i=0 ; i<s.length() ; i++)
    {
        char ch = s[i];
        string left = s.substr(0,i);
        string right= s.substr(i+1);
        string rest = left + right;
        if(checkPermutation(rest , permutation+ch,t))
            return true;
    }
   return false;
}
bool isAnagram(string s, string t) {
        string permutation="";
        return checkPermutation(s,permutation,t);
}

Approach - 2 [ O(nlogn) ]
If we rearrange both the strings in a particular way and if both strings are found equal then that means they are anagrams of each other.

We can use a sorting algorithm to arrange both the strings in increasing order or decreasing order lexicographically and if both the strings are anagrams of each other then they must be equal after sorting.

bool isAnagram(string s, string t) {
      sort(begin(s),end(s));
      sort(begin(t),end(t));
      return s==t;  
}

Approach - 3 [ O(n) ]
In approach-2 we checked equality after sorting the strings and equality is possible only if both the strings have the same count of each character present in it.

Also, rearranging means we can use any method to rearrange characters. So, if only count the characters of both strings and if the count of all the characters in string s is the same as the count of each respective character in string t then s and t are anagrams of each other.

bool isAnagram(string s, string t) {
        if(s.length()!=t.length()) return false;

        unordered_map<char,int> count_s;
        unordered_map<char,int> count_t;

        for(auto x:s){
            count_s[x]++;
        }

        for(auto x:t){
            count_t[x]++;
        }

        for(auto x:s){
            if(count_s[x]!=count_t[x]) return false;
        }

        return true;
    }

This approach can be optimized further by using only one map.

bool isAnagram(string s, string t) {
        if(s.length()!=t.length()) return false;

        unordered_map<char,int> count;

        for(auto x:s){
            count[x]++;
        }

        for(auto x:t){
            count[x]--;
        }

        for(auto x:s){
            if(count[x]!=0) return false;
        }

        return true;
    }

That's all about this problem.

As a problem setter I can make more problems by adding some extra conditions in it, like:

• What if we can rearrange it only in a particular way?
• What if we have the ability to add some or remove some characters from the strings.

• As we know to rearrange the letters swapping is done and if we bind the maximum number of swaps allowed then what will happen?

  These are some conditions [ and many more ] which when added to this easy problem can make it medium or hard level.

But the basic concept will be the same.

Thank you for reading it!
Happy Learning 😃