Coding Interview PatternsValid Anagram
EasyHash Maps

Valid Anagram

Explanation & Solution

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

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

Output: true

Explanation: Rearranging the letters of "nagaram" produces "anagram".

Constraints

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

Approach

Hash Maps pattern

1. Quick Length Check

  • If the two strings have different lengths, they cannot be anagrams — return false immediately

2. Count Characters in s

  • Create a Map to store the frequency of each character in s
  • Iterate through s, incrementing the count for each character

3. Decrement Counts Using t

  • Iterate through t, and for each character:
  • If the character is not in the map or its count is 0, return false — t has an extra character not in s
  • Otherwise, decrement the count by 1

4. Return True

  • If we finish iterating through t without returning false, all characters match in frequency
  • Since both strings have the same length and all counts were properly decremented, t is a valid anagram of s

Key Insight

  • Two strings are anagrams if and only if they have the same character frequencies
  • Using a hash map to count characters in one string and decrement with the other avoids sorting
Time
O(n)two linear passes through the strings
Space
O(1)the map holds at most 26 entries (lowercase English letters)

Visualization

Input:
[a, n, a, g, r, a, m], t = nagaram
a0n1a2g3r4a5m6
—

No animation available

Left (L)Right (R)ConvergedDone
0 steps

Solution Code

Previous
Two Sum
Next
Group Anagrams