Valid Anagram DSA Solution - Frequency Map

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.

Input	Output	Why
`s = "anagram"`, `t = "nagaram"`	`true`	Both strings contain the same character counts.
`s = "rat"`, `t = "car"`	`false`	The character counts differ.

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

Step	Action	State
Build counts from `anagram`	Count each char	`a:3, n:1, g:1, r:1, m:1`
Read `n` from `nagaram`	Subtract 1	`n:0`
Read remaining chars	All counts stay valid	No missing or negative count
Finish	Return	`true`

Complexity

Measure	Value	Reason
Time	O(n)	Each string is scanned once.
Space	O(k)	`k` is the number of distinct characters stored.

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

Is sorting acceptable?

Yes, but it is O(n log n). Counting is usually better when character frequencies are enough.

Why check length first?

Strings of different lengths cannot have identical character frequencies.

What is the core pattern?

Frequency map comparison.

Valid Anagram: Frequency map Pattern