Valid Anagram: Frequency map Pattern

Learning Outcome

After this lesson, you should be able to decide when sorting is enough and when a frequency map is the cleaner linear-time solution.

Problem Statement

Given two strings s and t, return true if t is an anagram of s. An anagram uses the same characters with the same frequencies.

Brute Force Approach

Sort both strings and compare the sorted results. If they match, the strings are anagrams.

This is simple and valid, but sorting costs O(n log n). If the character set is small or counting is natural, a frequency approach is better.

Optimized Approach

First reject strings of different lengths. Then count every character in s and subtract counts while scanning t. If a count goes below zero or a character is missing, the strings are not anagrams.

Exact Pseudocode

if length(s) != length(t):
  return false
counts = empty map
for char in s:
  counts[char] = counts[char] + 1
for char in t:
  if char not in counts or counts[char] == 0:
    return false
  counts[char] = counts[char] - 1
return true
  

Reference Code

class Solution:
    def isAnagram(self, s, t):
        if len(s) != len(t):
            return False

        counts = {}
        for ch in s:
            counts[ch] = counts.get(ch, 0) + 1

        for ch in t:
            if counts.get(ch, 0) == 0:
                return False
            counts[ch] -= 1

        return True
  

Sample Dry Run

Complexity

Edge Cases

• Different lengths should immediately return false.
• Repeated characters such as multiple a values.
• Character set assumptions: lowercase English letters versus Unicode.

Interview Checklist

• Ask whether input is lowercase English only.
• Mention sorting as brute force or baseline.
• Use frequency counts for linear time.

FAQs