Valid Anagram

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 formed by rearranging all the letters of another word exactly once. Both strings must use the exact same characters with the exact same frequencies.

What to notice first

• Length check first: if len(s) != len(t), immediately return false.
• The key insight is that two strings are anagrams when they have identical character frequency maps.
• The hash map approach counts characters in O(n) and needs no extra sorting pass.

Examples

s	t	Output	Explanation
"anagram"	"nagaram"	true	Same letters, different order
"rat"	"car"	false	c appears in t but not s
"a"	"ab"	false	Different lengths

Constraints

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

Real-World Applications

Where this pattern appears

• Spell checker / autocomplete — detect if the user typed an anagram of a known word (e.g. a transposition typo).
• Plagiarism detection — check whether two tokenised sentences use the same vocabulary with the same frequency.
• Cryptogram solving — verify that a candidate decoded word uses exactly the letters of the cipher word.
• Password strength — flag passwords that are simple rearrangements of dictionary words.

Complexity Comparison

Approach	Time	Space	Best When
Hash Map	O(n)	O(1)*	General case — single pass, fast
Sorting	O(n log n)	O(n)	Code simplicity matters more than speed

* At most 26 distinct lowercase letters, so the map size is bounded by a constant.

Which approach should you learn first?

• Pick Hash Map for interviews — O(n) with constant extra space is the expected answer.
• Pick Sorting when you want the shortest possible implementation or are familiar with sort-based comparisons.

Best For Speed

Hash Map

O(n) time · O(1) space

Simplest Code

Sorting

O(n log n) time · O(n) space

Approach 1: Hash Map

★ Recommended

Count each character’s frequency in s with a hash map, then subtract for each character in t. If every count returns to zero, the strings are anagrams. An early-exit check on lengths avoids unnecessary work.

⏱ Time O(n) Two passes of length n 💾 Space O(1) At most 26 keys — constant

Step-by-step Example

Input: s = "rat", t = "tar"

Phase	char	Map state
Count s	r	{r:1}
Count s	a	{r:1, a:1}
Count s	t	{r:1, a:1, t:1}
Subtract t	t	{r:1, a:1, t:0}
Subtract t	a	{r:1, a:0, t:0}
Subtract t	r	{r:0, a:0, t:0}
All zero?	—	Yes → return true

Animated walkthrough

How frequency counting determines an anagram

Use Next or Autoplay to watch characters from s build up the count map, then characters from t subtract from it.

Back Autoplay Next Reset

Step 1 of 4

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function isAnagram(s, t):
    if len(s) != len(t): return false
    freq = {}
    for char in s: freq[char] = freq.get(char, 0) + 1
    for char in t:
        freq[char] = freq.get(char, 0) - 1
        if freq[char] < 0: return false
    return true

Solution Code

Python

valid_anagram_hash_map.py

from collections import Counter


def is_anagram(s: str, t: str) -> bool:
    return Counter(s) == Counter(t)

C++

valid_anagram_hash_map.cpp

#include <string>
#include <unordered_map>
using namespace std;

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) return false;
        unordered_map<char, int> count;
        for (char ch : s) count[ch]++;
        for (char ch : t) {
            if (!count.count(ch)) return false;
            count[ch]--;
            if (count[ch] == 0) count.erase(ch);
        }
        return count.empty();
    }
};

Java

valid_anagram_hash_map.java

import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        Map<Character, Integer> count = new HashMap<>();
        for (char ch : s.toCharArray()) count.put(ch, count.getOrDefault(ch, 0) + 1);
        for (char ch : t.toCharArray()) {
            if (!count.containsKey(ch)) return false;
            count.put(ch, count.get(ch) - 1);
            if (count.get(ch) == 0) count.remove(ch);
        }
        return count.isEmpty();
    }
}

JavaScript

valid_anagram_hash_map.js

function isAnagram(s, t) {
    if (s.length !== t.length) return false;
    const count = new Map();
    for (const ch of s) count.set(ch, (count.get(ch) || 0) + 1);
    for (const ch of t) {
        if (!count.has(ch)) return false;
        count.set(ch, count.get(ch) - 1);
        if (count.get(ch) === 0) count.delete(ch);
    }
    return count.size === 0;
}

Rust

valid_anagram_hash_map.rs

use std::collections::HashMap;

impl Solution {
    pub fn is_anagram(s: String, t: String) -> bool {
        if s.len() != t.len() {
            return false;
        }
        let mut count = HashMap::new();
        for ch in s.chars() {
            *count.entry(ch).or_insert(0) += 1;
        }
        for ch in t.chars() {
            if let Some(value) = count.get_mut(&ch) {
                *value -= 1;
                let should_remove = *value == 0;
                if should_remove {
                    count.remove(&ch);
                }
            } else {
                return false;
            }
        }
        count.is_empty()
    }
}

Go

valid_anagram_hash_map.go

func isAnagram(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }
    count := map[rune]int{}
    for _, ch := range s {
        count[ch]++
    }
    for _, ch := range t {
        if _, ok := count[ch]; !ok {
            return false
        }
        count[ch]--
        if count[ch] == 0 {
            delete(count, ch)
        }
    }
    return len(count) == 0
}

Approach 2: Sorting

✓ Simple

Sort both strings independently. If the sorted versions are equal, the original strings are anagrams — they contain the same characters in the same quantities, just in a different order.

⏱ Time O(n log n) Two sort passes 💾 Space O(n) Sorted char arrays

Step-by-step Example

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

Step	Value
sorted(s)	"aaagmnr"
sorted(t)	"aaagmnr"
Equal?	Yes → return true

Input: s = "rat", t = "car"

Step	Value
sorted(s)	"art"
sorted(t)	"acr"
Equal?	No → return false

Pseudocode

function isAnagram(s, t):
    return sorted(s) == sorted(t)

Solution Code

Python

valid_anagram_sort.py

def is_anagram(s: str, t: str) -> bool:
    return sorted(s) == sorted(t)


print(is_anagram("anagram", "nagaram"))  # True
print(is_anagram("rat", "car"))          # False

C++

valid_anagram_sort.cpp

#include <algorithm>
#include <string>
using namespace std;

class Solution {
public:
    bool isAnagram(string s, string t) {
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return s == t;
    }
};

Java

valid_anagram_sort.java

import java.util.Arrays;

class Solution {
    public boolean isAnagram(String s, String t) {
        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();
        Arrays.sort(sArr);
        Arrays.sort(tArr);
        return Arrays.equals(sArr, tArr);
    }
}

JavaScript

valid_anagram_sort.js

function isAnagram(s, t) {
    return s.split('').sort().join('') === t.split('').sort().join('');
}

Rust

valid_anagram_sort.rs

impl Solution {
    pub fn is_anagram(s: String, t: String) -> bool {
        let mut s_chars: Vec<char> = s.chars().collect();
        let mut t_chars: Vec<char> = t.chars().collect();
        s_chars.sort_unstable();
        t_chars.sort_unstable();
        s_chars == t_chars
    }
}

Go

valid_anagram_sort.go

import "sort"

func isAnagram(s string, t string) bool {
  if len(s) != len(t) {
    return false
  }
  sRunes := []rune(s)
  tRunes := []rune(t)
  sort.Slice(sRunes, func(i, j int) bool { return sRunes[i] < sRunes[j] })
  sort.Slice(tRunes, func(i, j int) bool { return tRunes[i] < tRunes[j] })
  return string(sRunes) == string(tRunes)
}

Watch for these pitfalls

• Forgetting the length check — if s and t have different lengths they cannot be anagrams, so check this first.
• Using a map key that doesn’t exist — decrement before checking can produce negative counts; always initialise missing keys to 0 first.
• Unicode follow-up: the constraint here guarantees lowercase ASCII, but in a real system you would want to handle Unicode correctly (use code points, not bytes).

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

valid_anagram_space_optimized.py

"""
Solution for Valid Anagram
"""

def solve():
    """Implementation for approach 3 of Valid Anagram"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

valid_anagram_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Valid Anagram
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

ValidAnagramSpaceOptimized.java

/**
 * Solution for Valid Anagram
 * Approach 3
 */
public class ValidAnagramSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

valid_anagram_space_optimized.js

/**
 * Solution for Valid Anagram
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

valid_anagram_space_optimized.rs

/// Solution for Valid Anagram
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

valid_anagram_space_optimized.go

package main

import "fmt"

// Solution for Valid Anagram
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Two Sum Easy #1
• Contains Duplicate Easy #217
• Group Anagrams ↗ Medium #49
• Find All Anagrams in a String ↗ Medium #438

Interview Tips

Key trade-offs to discuss

• Why hash map over sorting? O(n) vs O(n log n). The map approach also lets you exit early the moment a character goes negative.
• Constant space claim: with only lowercase English letters the map has at most 26 keys — technically O(1) space even though a map is used.
• Follow-up — Unicode strings? The same hash map approach works; the bound on map size increases but the algorithm stays O(n).
• Follow-up — streams? You cannot sort a stream, so the hash map approach is the only viable one for streaming input.

← Previous
#238 Product of Array Except Self Next
#268 Missing Number →