Log inSign up
easyleetcodeNot Started

Valid Anagram

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

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 1:

Input: s = "anagram", t = "nagaram"
Output: true
Explanation: Both strings contain the exact same characters with identical frequencies: a:3, g:1, m:1, n:1, r:1.

Example 2:

Input: s = "rat", t = "car"
Output: false
Explanation: Characters differ, not an anagram.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Verify string permutations using frequency counters.
  • Implement single-pass differential balance counting.
  • Compare trade-offs between sorting and frequency hashing.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Checking if one string is an exact permutation/rearrangement of another.
  • Comparing character distributions with identical length constraints.

Algorithmic Decision Tree:

  • Checking if one string is an exact permutation/rearrangement of another.
  • Comparing character distributions with identical length constraints.

Connected Patterns:

Group AnagramsFind All Anagrams in a StringValid Palindrome

1. Sort Both Strings

Intuition

If s and t have different lengths, return false. Sort characters of s and sort characters of t. If sorted s equals sorted t, return true; otherwise, return false.

When to apply: Basic baseline comparison.

Algorithm

  1. If s.length != t.length: return false.
  2. Sort s.
  3. Sort t.
  4. Return s == t.

Sorting Both Strings & Direct Equality Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, n, a, g, r, a, m]
Current operationSTEP 1 OF 6
Observation: Compare string lengths
Visual state
Values and pointers at this exact step
array
S
a
n
a
g
r
a
m
0
1
2
3
4
5
6
Variables at this step
s.length
7
t.length
7
Equal Lengths
true
Check / comparison
Check lengths: s.length (7) == t.length (7). Lengths match.
Decision / next transition
Equal length condition satisfied. Proceed to sort both strings.
Why this step matters

Observation: Compare string lengths. s.length == t.length == 7.

Decision: If lengths differed, they could never be anagrams. Since equal, continue to sorting.

Invariant: Candidate pair has equal size.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <algorithm>
4
5class Solution {
6public:
7 bool isAnagram(std::string s, std::string t) {
8 if (s.size() != t.size()) return false;
9 std::sort(s.begin(), s.end());
10 std::sort(t.begin(), t.end());
11 return s == t;
12 }
13};
14
15int main() {
16 Solution sol;
17 std::cout << (sol.isAnagram("anagram", "nagaram") ? "true" : "false") << std::endl; // true
18 std::cout << (sol.isAnagram("rat", "car") ? "true" : "false") << std::endl; // false
19 return 0;
20}

Time & Space Complexity

  • Time complexity: O(N log N) — Sorting N characters takes O(N log N) time.
  • Space complexity: O(1) or O(N)

Why Brute Force Doesn't Scale:

Single loop computes increments and decrements simultaneously.

26-element integer array allocated on the stack.

2. Hash Map Multiplicity Counting (Unicode Support)

Intuition

If lengths differ, return false. Maintain a hash map. For each character in s, increment its count. For each character in t, decrement its count and return false if count drops below 0. Return true.

When to apply: When inputs contain arbitrary Unicode or international characters.

Algorithm

  1. If s.length != t.length: return false.
  2. Initialize map = {}.
  3. For c in s: map[c] = (map[c] || 0) + 1.
  4. For c in t:
  5. If !map[c] || map[c] == 0: return false.
  6. map[c]--.
  7. Return true.

Hash Map Multiplicity Counting with Unicode Support Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, n, g, r, m]
Current operationSTEP 1 OF 6
Observation: Scan s = "anagram" and populate hash map with character frequencies
Visual state
Values and pointers at this exact step
array
S
a:3
n:1
g:1
r:1
m:1
0
↑ TALLY S
1
2
3
4
Variables at this step
Map Entries
5
Total Frequency
7
Check / comparison
Pass 1: Count characters of s = "anagram" into Hash Map.
Decision / next transition
Map holds { a: 3, n: 1, g: 1, r: 1, m: 1 }.
Why this step matters

Observation: Scan s = "anagram" and populate hash map with character frequencies.

Decision: counts = { 'a': 3, 'n': 1, 'g': 1, 'r': 1, 'm': 1 }.

Invariant: Captures full frequency distribution of s.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <unordered_map>
4
5class Solution {
6public:
7 bool isAnagram(std::string s, std::string t) {
8 if (s.size() != t.size()) return false;
9 std::unordered_map<char, int> count;
10 for (char c : s) count[c]++;
11 for (char c : t) {
12 if (--count[c] < 0) return false;
13 }
14 return true;
15 }
16};
17
18int main() {
19 Solution sol;
20 std::cout << (sol.isAnagram("anagram", "nagaram") ? "true" : "false") << std::endl; // true
21 return 0;
22}

Time & Space Complexity

  • Time complexity: O(N) — Single linear pass inserting and decrementing hash map keys.
  • Space complexity: O(U) where U <= N

3. Fixed 26-Element Array Single-Pass (Optimal)

Intuition

Check s.length != t.length. Create count[26] initialized to 0. In a single loop over i from 0 to N - 1, increment count[s[i] - 'a']++ and decrement count[t[i] - 'a']--. Finally, verify all 26 entries are 0.

When to apply: The standard gold standard solution for maximum speed and zero memory allocation.

Algorithm

  1. If s.length != t.length: return false.
  2. Initialize count[26] = {0}.
  3. For i from 0 to s.length - 1:
  4. count[s[i] - 'a']++.
  5. count[t[i] - 'a']--.
  6. For x in count:
  7. If x != 0: return false.
  8. Return true.

Fixed 26-Bucket Frequency Balance Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, n, a, g, r, a, m]
Current operationSTEP 1 OF 6
Observation: Both strings have equal length (7)
Visual state
Values and pointers at this exact step
array
S
a
n
a
g
r
a
m
0
↑ i=0: 'a' vs 'n'
1
2
3
4
5
6
Variables at this step
Index
0
s[0]
a
t[0]
n
Delta Table
{ a: +1, n: -1 }
Check / comparison
s[0]='a' (+1), t[0]='n' (-1). Delta: { a: +1, n: -1 }.
Decision / next transition
Increment s[0], decrement t[0].
Why this step matters

Observation: Both strings have equal length (7). Initialize single frequency delta array of size 26.

Decision: Process index 0: increment count for s[0] (a), decrement count for t[0] (n).

Invariant: Anagram requires all 26 delta counts to return to exact 0 at the end.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 bool isAnagram(std::string s, std::string t) {
7 if (s.size() != t.size()) return false;
8 int count[26] = {0};
9 for (size_t i = 0; i < s.size(); ++i) {
10 count[s[i] - 'a']++;
11 count[t[i] - 'a']--;
12 }
13 for (int x : count) {
14 if (x != 0) return false;
15 }
16 return true;
17 }
18};
19
20int main() {
21 Solution sol;
22 std::cout << (sol.isAnagram("anagram", "nagaram") ? "true" : "false") << std::endl; // true
23 std::cout << (sol.isAnagram("rat", "car") ? "true" : "false") << std::endl; // false
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(N) strictly — Single linear pass over both strings and a 26-element loop.
  • Space complexity: O(1) extra space (26 integers)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Sorting ComparisonO(N log N)O(1) or O(N) depending on language sort implementationExtremely simple one-line check: sort(s) == sort(t).Log-linear time complexity.
2.Hash Map Frequency Counter (Unicode General)O(N)O(U) where U is number of unique charactersHandles arbitrary Unicode and emoji characters effortlessly.Hash table hashing overhead.
3.Fixed 26-Element Array (Optimal)OptimalO(N)O(1) extra spaceMaximum cache locality, single pass, zero heap allocations.Limited to lowercase English alphabet (can be sized to 256 for ASCII).

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Omitting the initial length equality check, causing index out-of-bounds or false positive scans.

Pitfall 2:

Using sum/XOR of ASCII values (e.g. ac vs bb have the same ASCII sum 196 and XOR, but are not anagrams).

Crucial Edge Cases to Validate:

  • Strings with different lengths (s = a, t = ab): Length mismatch check returns false in O(1) time.
  • Single character identical (s = a, t = a): count[a] balanced to 0, returns true.
  • Same characters but different frequencies (s = aa, t = a): Length mismatch returns false.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention how you would adapt the algorithm if inputs contain Unicode (use Hash Table).
  2. Explain why XOR or sum tricks are insufficient due to collision vulnerabilities.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does simple ASCII summation fail as a valid anagram test?

Back to DSA Sheet