LeetCode Solution 242 - Valid Anagram

Problem Statement

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

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= s.length, t.length <= 5 * 10^4
• s and t consist of lowercase English letters.

Optimal Approach

The most efficient way to check if two strings are anagrams is to count the frequency of each character in both strings and compare them.

Approach: Using HashMap / Frequency Array

• Create a frequency array of size 26 (since we have only lowercase English letters).
• Iterate over the first string and increment the frequency count.
• Iterate over the second string and decrement the frequency count.
• If all values in the frequency array remain zero, the strings are anagrams.

Code Implementation (C++)

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) return false;
        
        vector<int> count(26, 0);
        
        for (int i = 0; i < s.length(); i++) {
            count[s[i] - 'a']++;
            count[t[i] - 'a']--;
        }
        
        for (int num : count) {
            if (num != 0) return false;
        }
        
        return true;
    }
};

Step-by-Step Explanation

1. Edge Case Handling: If the lengths of s and t are different, return false immediately.
2. Frequency Array: Create a vector of size 26 initialized with 0.
3. Character Count Update:
   • Traverse s, increment the count at s[i] - 'a'.
   • Traverse t, decrement the count at t[i] - 'a'.
4. Final Validation: If all values in the frequency array are 0, return true; otherwise, return false.

Dry Run / Execution Steps

Consider s = "anagram", t = "nagaram".

Step	Character in s	Character in t	Count Array
1	'a' (+1)	'n' (-1)	a=1, n=-1
2	'n' (+1)	'a' (-1)	a=0, n=0
3	'a' (+1)	'g' (-1)	a=1, g=-1
4	'g' (+1)	'a' (-1)	a=0, g=0
5	'r' (+1)	'r' (-1)	r=0
6	'a' (+1)	'a' (-1)	a=0
7	'm' (+1)	'm' (-1)	m=0

All values are zero, hence output true.

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Sorting	O(n log n)	O(1) (in-place)	Sorting takes extra time
HashMap	O(n)	O(26) = O(1)	Optimal, but array is faster
Brute Force (Generating permutations)	O(n!)	O(n)	Exponential, not feasible

Best Solution & Why It’s Best

The best solution is using the frequency array because:

• It runs in O(n) time complexity.
• It uses only O(1) extra space (since the frequency array is fixed at 26 elements).
• Faster than sorting, as O(n log n) is avoided.

Complexity Analysis

• Sorting Approach: O(n log n) time, O(1) space (if sorted in-place).
• HashMap Approach: O(n) time, O(1) space (since max 26 characters).
• Best Approach (Frequency Array): O(n) time, O(1) space.

Conclusion

• The best way to check an anagram is using a frequency array.
• It is the most efficient method in terms of both time and space. 🚀