deepSWE.io

Valid Anagram

HashingStrings

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.

Example

String s:

String t:

Character Frequencies:

a×3

n×1

g×1

r×1

m×1

✓ Characters match - Valid Anagram!

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

Output: true

Explanation:

Both strings contain the same characters with the same frequencies
Each letter appears the same number of times in both strings
't' can be formed by rearranging letters in 's'

Key Properties

• Character frequency must match exactly
• Order of characters doesn't matter
• Case sensitive comparison
• Can use array or hash map for counting
• Both strings must be same length to be anagrams

Constraints

• 1 ≤ s.length, t.length ≤ 5 × 10⁴
• s and t consist of lowercase English letters

Solution Explanation

The solution uses a character frequency counting approach to determine if two strings are anagrams. By definition, anagrams must contain exactly the same characters with the same frequencies.

Key Steps

Check if both strings have the same length
Create a data structure to store character frequencies
Count frequencies of characters in first string
Verify frequencies match using second string
Ensure all character counts are zero

Time & Space Complexity

Time: O(n) where n is string length
Space: O(1) since we only store 26 letters
Single pass through each string
Fixed size array/map for frequency counting

Starting anagram check...

String s:

String t:

Character Count Map:

Valid Anagram Solutions

def isAnagram(self, s: str, t: str) -> bool:
    # If lengths are different, they can't be anagrams
    if len(s) != len(t):
        return False
    
    # Create a character frequency map
    char_map = {}
    
    # Count frequency of each character in s
    for char in s:
        char_map[char] = char_map.get(char, 0) + 1
    
    # Check against string t
    for char in t:
        # If character not in map or count becomes 0
        # strings are not anagrams
        if char not in char_map or char_map[char] == 0:
            return False
        char_map[char] -= 1
    
    # All counts should be 0 for valid anagram
    return all(count == 0 for count in char_map.values())