Valid Anagram

Given two strings, determine if one is an anagram of the 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, using all the original letters exactly once.

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: 'r', 'a', 't' vs 'c', 'a', 'r' -- the character sets differ.

Example 3:

Input: s = "listen", t = "silent"
Output: true
Explanation: "listen" and "silent" contain the exact same letters.

Constraints

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

Approach 1: Sorting

Algorithm

Sort both strings and compare them character by character. If the sorted forms are identical, the strings are anagrams.

Steps:

  1. If the lengths differ, return false immediately
  2. Sort both strings
  3. Compare the sorted strings for equality

Implementation

Python:

def isAnagram(s, t):
    """
    Check if two strings are anagrams by sorting
    Time: O(n log n)
    Space: O(n) for the sorted copies
    """
    if len(s) != len(t):
        return False

    return sorted(s) == sorted(t)

Java:

import java.util.*;

class Solution {
    /**
     * Check if two strings are anagrams by sorting
     * Time: O(n log n)
     * Space: O(n) for the character arrays
     */
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }

        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();

        Arrays.sort(sArr);
        Arrays.sort(tArr);

        return Arrays.equals(sArr, tArr);
    }
}

Go:

import "sort"

// isAnagram - Check if two strings are anagrams by sorting
// Time: O(n log n)
// Space: O(n) for rune slices
func isAnagram(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 by sorting
 * Time: O(n log n)
 * Space: O(n) for the sorted arrays
 */
function isAnagram(s, t) {
    if (s.length !== t.length) {
        return false;
    }

    return s.split('').sort().join('') === t.split('').sort().join('');
}

C#:

using System;

public class Solution {
    /// <summary>
    /// Check if two strings are anagrams by sorting
    /// Time: O(n log n)
    /// Space: O(n) for the character arrays
    /// </summary>
    public bool IsAnagram(string s, string t) {
        if (s.Length != t.Length) {
            return false;
        }

        char[] sArr = s.ToCharArray();
        char[] tArr = t.ToCharArray();

        Array.Sort(sArr);
        Array.Sort(tArr);

        return new string(sArr) == new string(tArr);
    }
}

Complexity Analysis

  • Time Complexity: O(n log n) - Dominated by the sorting step
  • Space Complexity: O(n) - Space for sorted copies of the strings

Approach 2: Hash Map Character Counting (Optimal)

Algorithm

Count the frequency of each character in both strings. If the frequency maps are identical, the strings are anagrams.

Steps:

  1. If the lengths differ, return false immediately
  2. Create a frequency array of size 26 (for lowercase English letters)
  3. Increment counts for characters in s, decrement for characters in t
  4. If all counts are zero, the strings are anagrams

Implementation

Python:

def isAnagram(s, t):
    """
    Check if two strings are anagrams using character frequency counting
    Time: O(n)
    Space: O(1) - fixed 26-element array
    """
    if len(s) != len(t):
        return False

    # Frequency array for 26 lowercase letters
    freq = [0] * 26

    for char in s:
        freq[ord(char) - ord('a')] += 1

    for char in t:
        freq[ord(char) - ord('a')] -= 1

    # All counts must be zero for anagrams
    for count in freq:
        if count != 0:
            return False

    return True

Java:

class Solution {
    /**
     * Check if two strings are anagrams using character frequency counting
     * Time: O(n)
     * Space: O(1) - fixed 26-element array
     */
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }

        // Frequency array for 26 lowercase letters
        int[] freq = new int[26];

        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }

        for (char c : t.toCharArray()) {
            freq[c - 'a']--;
        }

        // All counts must be zero for anagrams
        for (int count : freq) {
            if (count != 0) {
                return false;
            }
        }

        return true;
    }
}

Go:

// isAnagram - Check if two strings are anagrams using character frequency counting
// Time: O(n)
// Space: O(1) - fixed 26-element array
func isAnagram(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }

    // Frequency array for 26 lowercase letters
    var freq [26]int

    for _, ch := range s {
        freq[ch-'a']++
    }

    for _, ch := range t {
        freq[ch-'a']--
    }

    // All counts must be zero for anagrams
    for _, count := range freq {
        if count != 0 {
            return false
        }
    }

    return true
}

JavaScript:

/**
 * Check if two strings are anagrams using character frequency counting
 * Time: O(n)
 * Space: O(1) - fixed 26-element array
 */
function isAnagram(s, t) {
    if (s.length !== t.length) {
        return false;
    }

    // Frequency array for 26 lowercase letters
    const freq = new Array(26).fill(0);

    for (const ch of s) {
        freq[ch.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }

    for (const ch of t) {
        freq[ch.charCodeAt(0) - 'a'.charCodeAt(0)]--;
    }

    // All counts must be zero for anagrams
    for (const count of freq) {
        if (count !== 0) {
            return false;
        }
    }

    return true;
}

C#:

public class Solution {
    /// <summary>
    /// Check if two strings are anagrams using character frequency counting
    /// Time: O(n)
    /// Space: O(1) - fixed 26-element array
    /// </summary>
    public bool IsAnagram(string s, string t) {
        if (s.Length != t.Length) {
            return false;
        }

        // Frequency array for 26 lowercase letters
        int[] freq = new int[26];

        foreach (char c in s) {
            freq[c - 'a']++;
        }

        foreach (char c in t) {
            freq[c - 'a']--;
        }

        // All counts must be zero for anagrams
        foreach (int count in freq) {
            if (count != 0) {
                return false;
            }
        }

        return true;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Two linear passes through the strings
  • Space Complexity: O(1) - Fixed array of 26 elements regardless of input size

Key Insights

  1. Length Check First: If the two strings have different lengths, they cannot be anagrams, so return false immediately
  2. Frequency Counting: Two strings are anagrams if and only if every character appears the same number of times in both
  3. Fixed Array vs Hash Map: For lowercase English letters, a 26-element array is more efficient than a general hash map
  4. Increment/Decrement Trick: Incrementing for one string and decrementing for the other means a final check for all-zeros replaces two separate map comparisons
  5. Unicode Follow-up: If the character set is not restricted to lowercase letters, use a hash map instead of a fixed array

Edge Cases

  1. Different Lengths: s = “abc”, t = “ab” – return false immediately
  2. Empty Strings: s = “”, t = "" – both empty strings are trivially anagrams
  3. Single Character: s = “a”, t = “a” – true; s = “a”, t = “b” – false
  4. Same String: s = “hello”, t = “hello” – true, a string is an anagram of itself
  5. Repeated Characters: s = “aabb”, t = “abab” – true, same frequencies despite different order
  6. No Common Characters: s = “abc”, t = “xyz” – false

Test Cases

def test_isAnagram():
    # Basic anagram
    assert isAnagram("anagram", "nagaram") == True

    # Not an anagram
    assert isAnagram("rat", "car") == False

    # Classic anagram pair
    assert isAnagram("listen", "silent") == True

    # Different lengths
    assert isAnagram("abc", "ab") == False

    # Single character match
    assert isAnagram("a", "a") == True

    # Single character mismatch
    assert isAnagram("a", "b") == False

    # Repeated characters
    assert isAnagram("aabb", "abab") == True

    # Same string
    assert isAnagram("hello", "hello") == True

    # Nearly anagrams but one extra character
    assert isAnagram("aacc", "ccac") == False

    print("All tests passed!")

test_isAnagram()

Follow-up Questions

  1. Unicode Characters: What if the inputs contain Unicode characters? Use a hash map instead of a fixed array.
  2. Case Insensitive: What if the comparison should ignore case? Convert both strings to lowercase first.
  3. Group Anagrams: How would you group a list of strings by their anagram equivalence class?
  4. Find All Anagram Substrings: Given a string and a pattern, find all starting indices of the pattern’s anagrams in the string (sliding window).
  5. Minimum Deletions: What is the minimum number of character deletions to make two strings anagrams?

Common Mistakes

  1. Forgetting the Length Check: Skipping the early return when lengths differ, leading to incorrect true results
  2. Off-by-One in Index Mapping: Using ord(char) directly instead of ord(char) - ord('a'), causing array index out of bounds
  3. Using Wrong Data Structure: Using a hash map when a fixed array suffices, adding unnecessary overhead
  4. Not Handling All Characters: Assuming only alphabetic characters when the problem might include digits or special characters
  5. Comparing Maps Incorrectly: Building two separate frequency maps and comparing them key by key instead of using the increment/decrement approach

Interview Tips

  1. Clarify Constraints: Ask whether the input is restricted to lowercase English letters or could include Unicode
  2. Start Simple: Mention the sorting approach first, then optimize to frequency counting
  3. Explain the Key Insight: Two strings are anagrams iff they have identical character frequency distributions
  4. Discuss Space: Emphasize that the 26-element array is O(1) space, not O(n)
  5. Mention Follow-ups: Reference the sliding window variant (LeetCode #438) to show breadth of knowledge

Concept Explanations

Frequency Counting: The fundamental technique here is counting how often each character appears. This pattern recurs in many string and array problems.

Fixed Array vs Hash Map: When the character set is known and small (e.g., 26 lowercase letters), a fixed-size array is faster and uses less memory than a hash map due to no hashing overhead.

Increment-Decrement Pattern: By incrementing for one string and decrementing for the other, we reduce the problem to checking whether all entries in a single array are zero, which is simpler than comparing two separate maps.

Early Termination: Checking string lengths first avoids unnecessary work. This is a general optimization principle: eliminate impossible cases before doing expensive computation.