What pattern does Valid Anagram use?

The Pattern: Hash Maps (Frequency Counting) The Heuristic: When verifying if two collections contain the same elements with the same counts, transform each collection into a frequency map and compare these maps directly to achieve O(n) time complexity.

Valid Anagram — Hash Maps

Q: What is the time complexity of Valid Anagram?

O(n). The solution iterates through both strings once to build frequency maps, each operation O(1) on average, resulting in O(n) total time where n is the length of the strings.

Problem

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

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

Example

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

Output: true

The algorithm first checks if the lengths of s and t are equal. Since they are, it counts the frequency of each character in both strings. For s, the counts are {'a': 3, 'n': 1, 'g': 1, 'r': 1, 'm': 1}. For t, the counts are the same. Because the frequency dictionaries match exactly, the function returns true, confirming t is an anagram of s.

Approach

Straightforward Solution

A brute-force approach would generate all permutations of s and check if t matches any, which is factorial time and infeasible for large strings.

Core Observation

Two strings are anagrams if and only if they have identical character frequency distributions. This means counting characters in both strings and comparing these counts is sufficient to determine anagram status.

Path to Optimal

The key recognition signals are 'anagram' and 'same characters with same frequency'. These indicate Hash Maps because counting character occurrences and comparing frequency maps is an O(n) approach. By using hash maps (dictionaries) to count characters in both strings, the problem reduces to a simple equality check of these maps.

Optimal Approach

First, check if s and t have the same length; if not, return false immediately. Then, build two hash maps counting the frequency of each character in s and t respectively. Finally, compare these two maps for equality. If they match, return true; otherwise, false.

Time

O(n)

The solution iterates through both strings once to build frequency maps, each operation O(1) on average, resulting in O(n) total time where n is the length of the strings.

Space

O(1)

The auxiliary space is O(1) because the character set is fixed (lowercase English letters), so the frequency maps have at most 26 entries regardless of input size.

Solution

Python

1class Solution:
  def isAnagram(self, s: str, t: str) -> bool:
      if len(s) != len(t):
          return False
5
      s_counts = {}
      t_counts = {}
8
      for i in range(len(s)):
          s_counts[s[i]] = s_counts.get(s[i], 0) + 1
          t_counts[t[i]] = t_counts.get(t[i], 0) + 1
      
      return s_counts == t_counts

Step-by-Step Solution

1

Validate Length Equality to Quickly Reject Non-Anagrams

3if len(s) != len(t):
4    return False

Objective

To immediately return false if the input strings differ in length, as they cannot be anagrams.

Key Insight

Anagrams must have identical lengths because character counts must match exactly. This check avoids unnecessary computation for strings that cannot possibly be anagrams.

Interview Quick-Check

Core Logic

Length mismatch guarantees non-anagram status, enabling an early exit.

State & Boundaries

Check length before any frequency counting to optimize performance.

2

Build Frequency Maps for Both Strings in a Single Pass

6s_counts = {}
7t_counts = {}
9for i in range(len(s)):
10    s_counts[s[i]] = s_counts.get(s[i], 0) + 1
11    t_counts[t[i]] = t_counts.get(t[i], 0) + 1

Objective

To count the occurrences of each character in both strings simultaneously using hash maps.

Key Insight

Counting frequencies in one pass over the strings is efficient and leverages hash maps for O(1) average insertion and lookup. Doing both counts in the same loop reduces overhead and keeps the code concise.

Interview Quick-Check

Core Logic

Simultaneous frequency counting ensures O(n) time with minimal overhead.

Common Pitfalls & Bugs

Forgetting to initialize counts to zero or mishandling missing keys can cause incorrect frequency tallies.

3

Compare Frequency Maps to Confirm Anagram Status

13	`return s_counts == t_counts`

Objective

To determine if the two strings are anagrams by checking if their frequency maps are identical.

Key Insight

Hash map equality comparison is a direct and efficient way to verify that both strings have the exact same character counts, which is the defining property of anagrams.

Interview Quick-Check

Core Logic

Directly comparing frequency maps leverages built-in dictionary equality, simplifying correctness verification.

Common Pitfalls & Bugs

Comparing only keys or only values separately can lead to false positives; full map equality is required.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 13 Critical

return s_counts == t_counts

Return whether the two frequency maps are equal.

Equality of frequency maps directly confirms that both strings have identical character counts, which is the defining condition for anagrams.

Line 3 Critical

if len(s) != len(t):

Check if the lengths of s and t differ.

Anagrams must have the same length; this early check prevents unnecessary computation for strings that cannot be anagrams.

Line 10 Critical

s_counts[s[i]] = s_counts.get(s[i], 0) + 1

Increment the count of the current character in s_counts.

Updating the frequency map for s captures the exact number of occurrences of each character, which is essential for anagram verification.

Line 11 Critical

t_counts[t[i]] = t_counts.get(t[i], 0) + 1

Increment the count of the current character in t_counts.

Similarly, updating the frequency map for t ensures accurate character counts for comparison.

Line 4 Core

return False

Return false immediately if lengths differ.

Returning early here optimizes performance by avoiding needless frequency counting when an anagram is impossible.

Line 6 Core

s_counts = {}

Initialize an empty dictionary to count characters in s.

This dictionary will store character frequencies, enabling O(1) average-time updates and lookups.

Line 7 Core

t_counts = {}

Initialize an empty dictionary to count characters in t.

A separate dictionary is needed to independently track character frequencies in t for comparison.

Line 9 Standard

for i in range(len(s)):

Iterate over each index of the strings.

A single loop over the string length allows simultaneous frequency counting for both strings, ensuring O(n) time complexity.

Test Your Understanding

Why is comparing frequency maps sufficient to determine if two strings are anagrams?

Because an anagram requires the same characters with the same counts; frequency maps capture this information exactly, so equality of these maps guarantees anagram status.

Don't just read it. Drill it.

Reconstruct Valid Anagram from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Start drilling Valid Anagram for free

1	`class Solution:`
2	`def isAnagram(self, s: str, t: str) -> bool:`
3	`if len(s) != len(t):`
4	`return False`
5
6	`s_counts = {}`
7	`t_counts = {}`
8
9	`for i in range(len(s)):`
10	`s_counts[s[i]] = s_counts.get(s[i], 0) + 1`
11	`t_counts[t[i]] = t_counts.get(t[i], 0) + 1`
12
13	`return s_counts == t_counts`

6	`s_counts = {}`
7	`t_counts = {}`
9	`for i in range(len(s)):`
10	`s_counts[s[i]] = s_counts.get(s[i], 0) + 1`
11	`t_counts[t[i]] = t_counts.get(t[i], 0) + 1`

Problem

Example

Approach

Solution

Step-by-Step Solution

Validate Length Equality to Quickly Reject Non-Anagrams

Build Frequency Maps for Both Strings in a Single Pass

Compare Frequency Maps to Confirm Anagram Status

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.