Valid Anagram

Problem Link

242. Valid Anagram – LeetCode

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, typically using all original letters exactly once.

Examples

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⁴

• s and t consist of lowercase English letters.

Intuition

To check if t is an anagram of s, both strings must:

1. Be of equal length.

2. Contain exactly the same frequency of each character.

The problem becomes a character frequency comparison between two strings.

Approach: Frequency Array (Optimized for lowercase English letters)

1. If s.length() != t.length(), return false.

2. Initialize a frequency array freq[26] to track character counts.

3. Traverse both strings simultaneously:

   • Increment freq[s[i] - 'a']

   • Decrement freq[t[i] - 'a']

4. Finally, check if all elements in freq are zero. If yes, t is an anagram of s.

Java Code

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()) return false;

        int[] freq = new int[26];

        for (int i = 0; i < s.length(); i++) {
            freq[s.charAt(i) - 'a']++;
            freq[t.charAt(i) - 'a']--;
        }

        for (int count : freq) {
            if (count != 0) return false;
        }

        return true;
    }
}

Time and Space Complexity

Dry Run

Input:

s = "anagram", t = "nagaram"

Steps:

• Initialize freq[26] = all 0

• After traversing both strings:

  • All counts cancel out → all elements in freq = 0

• Return true

Follow-Up: Unicode Character Support

If s and t can contain Unicode characters, we cannot use a fixed-size array (since there are more than 26 characters).

Solution: Use a HashMap<Character, Integer> instead:

• Increment frequency for characters in s

• Decrement for characters in t

• If any frequency ≠ 0, return false

Time and space remain O(n), but the space is dynamic based on input charset.

Conclusion

This problem reinforces the classic frequency-counting technique, useful in problems related to anagrams, permutations, and character set comparisons.

For English letters, the fixed-size array approach is the most optimal.