LeetCodee

242. Valid Anagram

Jump to Solution: Python Java C++ JavaScript C#

Problem Description

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 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⁴
s and t consist of lowercase English letters

Follow up:

What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

Solution

Python Solution

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # If lengths are different, they can't be anagrams
        if len(s) != len(t):
            return False
            
        # Count characters in both strings
        char_count = {}
        
        # Count characters in s
        for char in s:
            char_count[char] = char_count.get(char, 0) + 1
            
        # Subtract counts for characters in t
        for char in t:
            if char not in char_count:
                return False
            charCount[char] -= 1
            if char_count[char] == 0:
                del char_count[char]
                
        # If all counts are zero, strings are anagrams
        return len(char_count) == 0

Time Complexity: O(n)

Where n is the length of the strings. We need to traverse both strings once.

Space Complexity: O(k)

Where k is the size of the character set. For lowercase English letters, k = 26.

Java Solution

class Solution {
    public boolean isAnagram(String s, String t) {
        // If lengths are different, they can't be anagrams
        if (s.length() != t.length()) {
            return false;
        }
        
        // Create array to store character counts (for lowercase letters)
        int[] charCount = new int[26];
        
        // Count characters in both strings
        for (int i = 0; i < s.length(); i++) {
            charCount[s.charAt(i) - 'a']++;
            charCount[t.charAt(i) - 'a']--;
        }
        
        // Check if all counts are zero
        for (int count : charCount) {
            if (count != 0) {
                return false;
            }
        }
        
        return true;
    }
}

Time Complexity: O(n)

Where n is the length of the strings. We need to traverse both strings once.

Space Complexity: O(1)

We use a fixed-size array of 26 characters.

C++ Solution

class Solution {
public:
    bool isAnagram(string s, string t) {
        // If lengths are different, they can't be anagrams
        if (s.length() != t.length()) {
            return false;
        }
        
        // Create array to store character counts (for lowercase letters)
        vector charCount(26, 0);
        
        // Count characters in both strings
        for (int i = 0; i < s.length(); i++) {
            charCount[s[i] - 'a']++;
            charCount[t[i] - 'a']--;
        }
        
        // Check if all counts are zero
        for (int count : charCount) {
            if (count != 0) {
                return false;
            }
        }
        
        return true;
    }
};

Time Complexity: O(n)

Where n is the length of the strings. We need to traverse both strings once.

Space Complexity: O(1)

We use a fixed-size vector of 26 characters.

JavaScript Solution

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    // If lengths are different, they can't be anagrams
    if (s.length !== t.length) {
        return false;
    }
    
    // Count characters in both strings
    const charCount = new Map();
    
    // Count characters in s
    for (const char of s) {
        charCount.set(char, (charCount.get(char) || 0) + 1);
    }
    
    // Subtract counts for characters in t
    for (const char of t) {
        if (!charCount.has(char)) {
            return false;
        }
        charCount.set(char, charCount.get(char) - 1);
        if (charCount.get(char) === 0) {
            charCount.delete(char);
        }
    }
    
    // If all counts are zero, strings are anagrams
    return charCount.size === 0;
};

Time Complexity: O(n)

Where n is the length of the strings. We need to traverse both strings once.

Space Complexity: O(k)

Where k is the size of the character set. For lowercase English letters, k = 26.

C# Solution

public class Solution {
    public bool IsAnagram(string s, string t) {
        // If lengths are different, they can't be anagrams
        if (s.Length != t.Length) {
            return false;
        }
        
        // Create array to store character counts (for lowercase letters)
        int[] charCount = new int[26];
        
        // Count characters in both strings
        for (int i = 0; i < s.Length; i++) {
            charCount[s[i] - 'a']++;
            charCount[t[i] - 'a']--;
        }
        
        // Check if all counts are zero
        foreach (int count in charCount) {
            if (count != 0) {
                return false;
            }
        }
        
        return true;
    }
}

Time Complexity: O(n)

Where n is the length of the strings. We need to traverse both strings once.

Space Complexity: O(1)

We use a fixed-size array of 26 characters.

Approach Explanation

The solution uses character counting to determine if two strings are anagrams:

Key Insight:
- Anagrams must have the same length
- Anagrams must have the same character counts
- We can use a single pass through both strings
Algorithm Steps:
- Check if lengths are equal
- Count characters (either using array or hash map)
- Verify all counts are zero

Example walkthrough for s = "anagram", t = "nagaram":

Initial check: lengths are equal (7)
Count characters in s: {a:3, n:1, g:1, r:1, m:1}
Subtract counts for t: all counts become 0
Final check: all counts are 0, so they are anagrams

Key insights:

Array-based solution is more efficient for ASCII
Hash map solution works for any character set
Early termination for different lengths
Single pass through both strings

Follow-up Solution:

For Unicode characters, use a hash map instead of fixed array
Space complexity becomes O(k) where k is unique characters
Time complexity remains O(n)
Works with any character set size