Valid Anagram

Determine if two strings are anagrams of each other

Language Selection

Choose your preferred programming language

Showing: Python

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

Input/Output Specifications

Input: Two strings s and t
Output: Boolean indicating if the strings are anagrams

Constraints

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

Examples

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true
Explanation: Both strings contain the same characters with the same frequencies.

Example 2:

Input: s = "rat", t = "car"
Output: false
Explanation: The strings have different character frequencies.

Example 3:

Input: s = "listen", t = "silent"
Output: true
Explanation: Both strings are anagrams of each other.

Solution Approaches

Approach 1: Character Frequency Count (Optimal)

Algorithm Explanation: Two strings are anagrams if they have the same character frequencies. We can use a frequency array to count characters in both strings and compare.

Check if strings have the same length
Create frequency array for lowercase letters (26 characters)
Count characters in first string (increment)
Count characters in second string (decrement)
Check if all frequencies are zero

Implementation:

Python:

def isAnagram(s, t):
    """
    Check if two strings are anagrams using frequency count
    Time: O(n)
    Space: O(1) - fixed size array
    """
    if len(s) != len(t):
        return False
    
    # Frequency array for lowercase letters
    freq = [0] * 26
    
    # Count characters in s (increment)
    for char in s:
        freq[ord(char) - ord('a')] += 1
    
    # Count characters in t (decrement)
    for char in t:
        freq[ord(char) - ord('a')] -= 1
    
    # Check if all frequencies are zero
    for count in freq:
        if count != 0:
            return False
    
    return True

Java:

class Solution {
    /**
     * Check if two strings are anagrams using frequency count
     * Time: O(n)
     * Space: O(1) - fixed size array
     */
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        
        // Frequency array for lowercase letters
        int[] freq = new int[26];
        
        // Count characters in s (increment)
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }
        
        // Count characters in t (decrement)
        for (char c : t.toCharArray()) {
            freq[c - 'a']--;
        }
        
        // Check if all frequencies are zero
        for (int count : freq) {
            if (count != 0) {
                return false;
            }
        }
        
        return true;
    }
}

Go:

// isAnagram - Check if two strings are anagrams using frequency count
// Time: O(n)
// Space: O(1) - fixed size array
func isAnagram(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }
    
    // Frequency array for lowercase letters
    freq := make([]int, 26)
    
    // Count characters in s (increment)
    for _, char := range s {
        freq[char-'a']++
    }
    
    // Count characters in t (decrement)
    for _, char := range t {
        freq[char-'a']--
    }
    
    // Check if all frequencies are zero
    for _, count := range freq {
        if count != 0 {
            return false
        }
    }
    
    return true
}

JavaScript:

/**
 * Check if two strings are anagrams using frequency count
 * Time: O(n)
 * Space: O(1) - fixed size array
 */
function isAnagram(s, t) {
    if (s.length !== t.length) {
        return false;
    }
    
    // Frequency array for lowercase letters
    const freq = new Array(26).fill(0);
    
    // Count characters in s (increment)
    for (let char of s) {
        freq[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    
    // Count characters in t (decrement)
    for (let char of t) {
        freq[char.charCodeAt(0) - 'a'.charCodeAt(0)]--;
    }
    
    // Check if all frequencies are zero
    for (let count of freq) {
        if (count !== 0) {
            return false;
        }
    }
    
    return true;
}

C#:

public class Solution {
    /// <summary>
    /// Check if two strings are anagrams using frequency count
    /// Time: O(n)
    /// Space: O(1) - fixed size array
    /// </summary>
    public bool IsAnagram(string s, string t) {
        if (s.Length != t.Length) {
            return false;
        }
        
        // Frequency array for lowercase letters
        int[] freq = new int[26];
        
        // Count characters in s (increment)
        foreach (char c in s) {
            freq[c - 'a']++;
        }
        
        // Count characters in t (decrement)
        foreach (char c in t) {
            freq[c - 'a']--;
        }
        
        // Check if all frequencies are zero
        foreach (int count in freq) {
            if (count != 0) {
                return false;
            }
        }
        
        return true;
    }
}

Complexity Analysis:

Time Complexity: O(n) - Single pass through both strings
Space Complexity: O(1) - Fixed size array of 26 elements

Trade-offs:

Optimal time and space complexity
Efficient for lowercase English letters
Simple and intuitive approach
Works well for constrained character sets

Approach 2: Hash Map (General Solution)

Algorithm Explanation: Use a hash map to count character frequencies. This approach works for any character set, not just lowercase letters.

Implementation:

Python:

def isAnagramHashMap(s, t):
    """
    Check if two strings are anagrams using hash map
    Time: O(n)
    Space: O(k) where k is the number of unique characters
    """
    if len(s) != len(t):
        return False
    
    # Count characters in s
    char_count = {}
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1
    
    # Check characters in t
    for char in t:
        if char not in char_count:
            return False
        char_count[char] -= 1
        if char_count[char] == 0:
            del char_count[char]
    
    return len(char_count) == 0

Java:

class Solution {
    /**
     * Check if two strings are anagrams using hash map
     * Time: O(n)
     * Space: O(k) where k is the number of unique characters
     */
    public boolean isAnagramHashMap(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        
        Map<Character, Integer> charCount = new HashMap<>();
        
        // Count characters in s
        for (char c : s.toCharArray()) {
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);
        }
        
        // Check characters in t
        for (char c : t.toCharArray()) {
            if (!charCount.containsKey(c)) {
                return false;
            }
            charCount.put(c, charCount.get(c) - 1);
            if (charCount.get(c) == 0) {
                charCount.remove(c);
            }
        }
        
        return charCount.isEmpty();
    }
}

Go:

// isAnagramHashMap - Check if two strings are anagrams using hash map
// Time: O(n)
// Space: O(k) where k is the number of unique characters
func isAnagramHashMap(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }
    
    charCount := make(map[rune]int)
    
    // Count characters in s
    for _, char := range s {
        charCount[char]++
    }
    
    // Check characters in t
    for _, char := range t {
        if count, exists := charCount[char]; !exists || count == 0 {
            return false
        }
        charCount[char]--
        if charCount[char] == 0 {
            delete(charCount, char)
        }
    }
    
    return len(charCount) == 0
}

JavaScript:

/**
 * Check if two strings are anagrams using hash map
 * Time: O(n)
 * Space: O(k) where k is the number of unique characters
 */
function isAnagramHashMap(s, t) {
    if (s.length !== t.length) {
        return false;
    }
    
    const charCount = new Map();
    
    // Count characters in s
    for (let char of s) {
        charCount.set(char, (charCount.get(char) || 0) + 1);
    }
    
    // Check characters in t
    for (let char of t) {
        if (!charCount.has(char)) {
            return false;
        }
        charCount.set(char, charCount.get(char) - 1);
        if (charCount.get(char) === 0) {
            charCount.delete(char);
        }
    }
    
    return charCount.size === 0;
}

C#:

public class Solution {
    /// <summary>
    /// Check if two strings are anagrams using hash map
    /// Time: O(n)
    /// Space: O(k) where k is the number of unique characters
    /// </summary>
    public bool IsAnagramHashMap(string s, string t) {
        if (s.Length != t.Length) {
            return false;
        }
        
        Dictionary<char, int> charCount = new Dictionary<char, int>();
        
        // Count characters in s
        foreach (char c in s) {
            if (charCount.ContainsKey(c)) {
                charCount[c]++;
            } else {
                charCount[c] = 1;
            }
        }
        
        // Check characters in t
        foreach (char c in t) {
            if (!charCount.ContainsKey(c)) {
                return false;
            }
            charCount[c]--;
            if (charCount[c] == 0) {
                charCount.Remove(c);
            }
        }
        
        return charCount.Count == 0;
    }
}

Complexity Analysis:

Time Complexity: O(n) - Single pass through both strings
Space Complexity: O(k) - Where k is the number of unique characters

Trade-offs:

Works for any character set
Higher space complexity for large character sets
More flexible than fixed array approach
Good for Unicode characters

Approach 3: Sorting (Not Optimal)

Algorithm Explanation: Sort both strings and compare them. If they are anagrams, the sorted versions will be identical.

Implementation:

Python:

def isAnagramSorting(s, t):
    """
    Check if two strings are anagrams using sorting
    Time: O(n log n)
    Space: O(1) - assuming in-place sorting
    """
    if len(s) != len(t):
        return False
    
    return sorted(s) == sorted(t)

Java:

class Solution {
    /**
     * Check if two strings are anagrams using sorting
     * Time: O(n log n)
     * Space: O(1) - assuming in-place sorting
     */
    public boolean isAnagramSorting(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        
        char[] sArray = s.toCharArray();
        char[] tArray = t.toCharArray();
        
        Arrays.sort(sArray);
        Arrays.sort(tArray);
        
        return Arrays.equals(sArray, tArray);
    }
}

Go:

// isAnagramSorting - Check if two strings are anagrams using sorting
// Time: O(n log n)
// Space: O(1) - assuming in-place sorting
func isAnagramSorting(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }
    
    sRunes := []rune(s)
    tRunes := []rune(t)
    
    sort.Slice(sRunes, func(i, j int) bool {
        return sRunes[i] < sRunes[j]
    })
    
    sort.Slice(tRunes, func(i, j int) bool {
        return tRunes[i] < tRunes[j]
    })
    
    return string(sRunes) == string(tRunes)
}

JavaScript:

/**
 * Check if two strings are anagrams using sorting
 * Time: O(n log n)
 * Space: O(1) - assuming in-place sorting
 */
function isAnagramSorting(s, t) {
    if (s.length !== t.length) {
        return false;
    }
    
    return s.split('').sort().join('') === t.split('').sort().join('');
}

C#:

public class Solution {
    /// <summary>
    /// Check if two strings are anagrams using sorting
    /// Time: O(n log n)
    /// Space: O(1) - assuming in-place sorting
    /// </summary>
    public bool IsAnagramSorting(string s, string t) {
        if (s.Length != t.Length) {
            return false;
        }
        
        char[] sArray = s.ToCharArray();
        char[] tArray = t.ToCharArray();
        
        Array.Sort(sArray);
        Array.Sort(tArray);
        
        return new string(sArray) == new string(tArray);
    }
}

Complexity Analysis:

Time Complexity: O(n log n) - Due to sorting
Space Complexity: O(1) - Assuming in-place sorting

Trade-offs:

Simple to understand and implement
Higher time complexity
Works for any character set
Not optimal for this problem

Key Insights

Anagram Definition: Two strings are anagrams if they have the same character frequencies
Length Check: Different lengths immediately indicate non-anagrams
Frequency Counting: The most efficient approach for this problem
Character Set Optimization: Fixed array works well for constrained character sets

Edge Cases

Empty Strings: "" and "" → Returns true
Single Character: "a" and "a" → Returns true
Different Lengths: "abc" and "ab" → Returns false
Same String: "hello" and "hello" → Returns true
No Common Characters: "abc" and "def" → Returns false
Repeated Characters: "aabb" and "abab" → Returns true

How Solutions Handle Edge Cases:

Length check handles different lengths immediately
Frequency counting works correctly for all cases
Empty strings are handled naturally
Repeated characters are counted correctly

Test Cases

def test_isAnagram():
    # Basic cases
    assert isAnagram("anagram", "nagaram") == True
    assert isAnagram("rat", "car") == False
    assert isAnagram("listen", "silent") == True
    
    # Edge cases
    assert isAnagram("", "") == True
    assert isAnagram("a", "a") == True
    assert isAnagram("abc", "ab") == False
    assert isAnagram("hello", "hello") == True
    assert isAnagram("abc", "def") == False
    assert isAnagram("aabb", "abab") == True
    
    # Case sensitivity (if applicable)
    # assert isAnagram("Hello", "hello") == False  # Depends on problem constraints
    
    print("All tests passed!")

test_isAnagram()

Follow-up Questions

Group Anagrams: How would you group all anagrams together in a list of strings?
Case Insensitive: What if the comparison should be case-insensitive?
Unicode Support: How would you handle Unicode characters?
Partial Anagrams: What if you only need to check if one string is a partial anagram of another?
Anagram Substrings: How would you find all anagram substrings in a string?

Common Mistakes

Not Checking Lengths: Forgetting to check if strings have the same length
- Problem: Incorrect results for different length strings
- Solution: Always check lengths first
Wrong Character Mapping: Incorrectly mapping characters to array indices
- Problem: Array index out of bounds or wrong counts
- Solution: Use ord(char) - ord('a') for lowercase letters
Not Handling Empty Maps: Not properly handling empty hash maps
- Problem: Incorrect results when all characters cancel out
- Solution: Check if map is empty after processing
Case Sensitivity: Not considering case sensitivity requirements
- Problem: Incorrect results for mixed case strings
- Solution: Clarify requirements and normalize if needed

Interview Tips

Start with Definition: Clearly define what an anagram means
Discuss Approaches: Mention sorting, hash map, and frequency array approaches
Optimize: Start with sorting, then optimize to frequency counting
Handle Edge Cases: Always discuss empty strings and different lengths
Space-Time Trade-offs: Discuss the trade-offs between different approaches

Concept Explanations

Frequency Counting: This problem demonstrates the fundamental technique of counting character frequencies, which is useful in many string problems.

Hash Map vs Array: Shows when to use fixed-size arrays vs hash maps based on the character set constraints.

Anagram Pattern: Understanding anagrams helps with many string manipulation problems and is a common interview topic.

Character Encoding: Understanding how characters map to array indices is crucial for efficient string processing.