Problem Overview

  • We are given s and t of length m and n respectively
  • We need to check if t is a valid anagram of s or not.
  • All characters will be in lowercase.
  • Note — An anagram is a word or phrase that is built by rearranging the characters of another word in a different order to form a new word.

Example


Input: s = "anagram", t = "nagaram"
Output: true


Input: s = "rat", t = "car"
Output: false

Brute Force

Intuition

  • If t and s are not of the same size, then they cannot be valid anagrams.
  • If all the characters present in s are present in t with the same frequency, then it is a valid anagram.
  • Use an array to store the frequency of characters from s.
  • Then iterate over t and decrease the frequency.
  • Finally iterate over the array — if anything other than 0 is present, then it is invalid.

Code

class Solution {
public:
 bool isAnagram(string s, string t) {
     if(s.size() != t.size()) return false;

     vector<int> freq = vector<int>(26, 0);

     for(auto it: t){
         freq[it-'a']++;
     }

     for(auto it: s){
         freq[it-'a']--;
     }

     for(auto it: freq){
         if(it != 0) return false;
     }

     return true;
 }
};

Time & Space Complexity

  • Time - O(n)
  • Space - O(26) → O(1)

Optimization

Intuition

  • Instead of checking validity in a separate loop, we can decrease the frequency and check it in the same loop.
  • To further optimize, we can use a fixed-size array instead of a vector.

Code

class Solution {
public:
 bool isAnagram(string s, string t) {

     if(s.size() != t.size()) return false;

     int freq[26] = {0};

     for(char c : s) freq[c-'a']++;

     for(char c : t)
         if(--freq[c-'a'] < 0) return false;

     return true;
 }
};

Time & Space Complexity

  • Time - O(n)
  • Space - O(26) → O(1)

Key Takeaways

  • You need to understand what an anagram is before solving the problem.
  • Observe and try to reduce unnecessary iterations if possible.