Valid Anagram

Description

Given two strings s and t, determine whether t is an anagram of s. Return true if it is, and false otherwise.

An anagram is a word or phrase formed by rearranging the letters of another word or phrase, using every original letter exactly once. In other words, two strings are anagrams if and only if they contain the same characters with the same frequencies — just in a different order.

Examples

Example 1

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

Output: true

Explanation: Both strings contain exactly the same letters: three 'a's, one 'n', one 'g', one 'r', and one 'm'. Since every letter appears the same number of times in both strings, they are anagrams of each other.

Example 2

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

Output: false

Explanation: The string "rat" contains 'r', 'a', 't', while "car" contains 'c', 'a', 'r'. The letter 't' appears in "rat" but not in "car", and the letter 'c' appears in "car" but not in "rat". Since the character sets differ, these are not anagrams.

Example 3

Input: s = "a", t = "a"

Output: true

Explanation: Both strings consist of the single character 'a'. They are trivially anagrams of each other.

Constraints

1 ≤ s.length, t.length ≤ 5 × 10^4
s and t consist of lowercase English letters only

Editorial

Brute Force

Intuition

The simplest way to check if two strings are anagrams is to sort both of them. If two strings are anagrams, they contain exactly the same characters — just scrambled. Sorting arranges every character in a predictable alphabetical order. Once both strings are sorted, they will look identical if and only if they started with the same characters at the same frequencies.

Think of it like organizing two messy drawers of lettered tiles. If you line up the tiles in each drawer from A to Z, identical drawers will produce the same arrangement.

Step-by-Step Explanation

Let's trace through with s = "rat", t = "car":

Step 1: Check lengths — len(s) = 3, len(t) = 3. They match, so we proceed. If they differed, we'd immediately return false.

Step 2: Sort string s = "rat" → sorted_s = "art".

Step 3: Sort string t = "car" → sorted_t = "acr".

Step 4: Compare sorted_s and sorted_t character by character:

Position 0: 'a' vs 'a' → match
Position 1: 'r' vs 'c' → mismatch!

Step 5: Since the sorted strings differ, return false. The strings are not anagrams.

Now let's also verify a true case: s = "anagram", t = "nagaram":

sorted_s = "aaagmnr"
sorted_t = "aaagmnr"
Every position matches → return true.

Sorting-Based Anagram Check: "rat" vs "car" — Watch how sorting both strings reveals whether they share the same characters. After sorting, a simple left-to-right comparison determines the answer.

Algorithm

If the lengths of s and t differ, return false immediately — anagrams must have the same number of characters.
Sort both strings alphabetically.
Compare the two sorted strings character by character.
If the sorted strings are identical, return true. Otherwise, return false.

Code

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

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

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        
        return sorted(s) == sorted(t)

import java.util.Arrays;

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();
        
        Arrays.sort(sChars);
        Arrays.sort(tChars);
        
        return Arrays.equals(sChars, tChars);
    }
}

Complexity Analysis

Time Complexity: O(n log n)

Sorting each string of length n takes O(n log n) time. The comparison afterwards is O(n). The dominant term is the sorting step, giving us O(n log n) overall, where n is the length of the strings.

Space Complexity: O(n) or O(1)

In languages where strings are immutable (Python, Java), sorting creates new copies of the strings, requiring O(n) space. In C++, where strings can be sorted in-place, auxiliary space is O(1) (ignoring the sort's internal stack).

Why This Approach Is Not Efficient

The sorting approach runs in O(n log n) time. With strings up to 5 × 10^4 characters, this is roughly 5 × 10^4 × 17 ≈ 8.5 × 10^5 operations — perfectly fast in practice.

However, the question is: do we really need to sort? Sorting rearranges the entire string just so we can compare character-by-character. But all we actually care about is whether each character appears the same number of times in both strings. We don't need any particular order — we just need to count.

Key insight: if we count the frequency of every character in both strings and compare those counts, we can answer the question in O(n) time without sorting. This reduces the time complexity from O(n log n) to O(n) — a meaningful improvement, especially as a foundation for understanding hash-based techniques.

Better Approach - Hash Map Frequency Count

Intuition

Instead of sorting, we can count how many times each character appears in each string using hash maps (dictionaries). If two strings are anagrams, every character will have the same count in both maps.

Imagine you have two bags of alphabet magnets. To check if they contain the same magnets, you could sort them both — or you could simply count the magnets of each letter in each bag and compare the tallies. The counting approach is faster because you only need to scan each bag once.

We build two separate frequency maps — one for each string — and then check if the maps are identical.

Step-by-Step Explanation

Let's trace through with s = "anagram", t = "nagaram":

Step 1: Check lengths — len(s) = 7, len(t) = 7. They match.

Step 2: Build frequency map for s = "anagram":

'a': process 'a' → count_s = {a:1}
'n': process 'n' → count_s = {a:1, n:1}
'a': process 'a' → count_s = {a:2, n:1}
'g': process 'g' → count_s = {a:2, n:1, g:1}
'r': process 'r' → count_s = {a:2, n:1, g:1, r:1}
'a': process 'a' → count_s = {a:3, n:1, g:1, r:1}
'm': process 'm' → count_s = {a:3, n:1, g:1, r:1, m:1}

Step 3: Build frequency map for t = "nagaram":

count_t = {n:1, a:3, g:1, r:1, m:1}

Step 4: Compare count_s and count_t — they are identical. Return true.

Hash Map Frequency Count — Two-Map Comparison — Watch how we build frequency counts for both strings and then compare them. If every character has the same count in both maps, the strings are anagrams.

Algorithm

If the lengths of s and t differ, return false immediately.
Create two hash maps (dictionaries) to store character frequencies.
Iterate through both strings simultaneously:
- For each character in s, increment its count in the first map.
- For each character in t, increment its count in the second map.
Compare the two frequency maps.
If the maps are identical, return true. Otherwise, return false.

Code

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

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) {
            return false;
        }
        
        unordered_map<char, int> countS, countT;
        
        for (int i = 0; i < s.length(); i++) {
            countS[s[i]]++;
            countT[t[i]]++;
        }
        
        return countS == countT;
    }
};

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

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> countS = new HashMap<>();
        Map<Character, Integer> countT = new HashMap<>();
        
        for (int i = 0; i < s.length(); i++) {
            countS.merge(s.charAt(i), 1, Integer::sum);
            countT.merge(t.charAt(i), 1, Integer::sum);
        }
        
        return countS.equals(countT);
    }
}

Complexity Analysis

Time Complexity: O(n)

We scan each string once to build the frequency maps — that is O(n) for each string. Comparing two hash maps with at most 26 keys is O(1). Total: O(n), where n is the length of the strings.

Space Complexity: O(1)

Although we use two hash maps, the number of distinct keys is bounded by 26 (lowercase English letters). This is a constant that does not grow with input size, so space complexity is O(1).

Why This Approach Is Not Efficient

The two-map approach is already O(n) in time and O(1) in space (since the character set is fixed at 26). However, it uses two separate hash maps and requires a final comparison step between them.

We can do better in terms of constant factors and simplicity. Instead of maintaining two separate maps, we can use a single frequency array of size 26 (one slot per lowercase letter). We increment counts for characters in s and decrement for characters in t. If the strings are anagrams, every slot will return to zero.

This eliminates hash map overhead (hashing, collision handling) and replaces it with direct array indexing, which is faster in practice. It also uses only one data structure instead of two, making the code cleaner.

Optimal Approach - Single Frequency Array

Intuition

Since the problem guarantees lowercase English letters only, there are at most 26 distinct characters. We can replace hash maps with a fixed-size array of 26 integers, where index 0 represents 'a', index 1 represents 'b', and so on.

The elegant trick: instead of building two separate counts and comparing them, we use a single array. For each character in s, we increment the corresponding slot. For each character in t, we decrement it. If the strings are anagrams, every increment from s will be perfectly canceled by a decrement from t, leaving every slot at zero.

Think of it as a balance sheet. Characters from s are deposits, characters from t are withdrawals. If the account balances to zero for every letter, the two strings used exactly the same characters in exactly the same quantities.

Step-by-Step Explanation

Let's trace through with s = "rat", t = "car":

Step 1: Check lengths — len(s) = 3, len(t) = 3. They match, so we proceed.

Step 2: Initialize a frequency array of 26 zeros: count = [0, 0, 0, ..., 0].

Step 3: Process index 0: s[0] = 'r', t[0] = 'c'.

Increment count['r' - 'a'] = count[17] by 1 → count[17] = 1
Decrement count['c' - 'a'] = count[2] by 1 → count[2] = -1

Step 4: Process index 1: s[1] = 'a', t[1] = 'a'.

Increment count['a' - 'a'] = count[0] by 1 → count[0] = 1
Decrement count['a' - 'a'] = count[0] by 1 → count[0] = 0
The 'a' from s and 'a' from t cancel each other out.

Step 5: Process index 2: s[2] = 't', t[2] = 'r'.

Increment count['t' - 'a'] = count[19] by 1 → count[19] = 1
Decrement count['r' - 'a'] = count[17] by 1 → count[17] = 0

Step 6: Check the frequency array. Relevant slots: count[0]=0, count[2]=-1, count[17]=0, count[19]=1.

count[2] = -1 (extra 'c' in t), count[19] = 1 (extra 't' in s). Not all zeros.

Step 7: Return false — the strings are not anagrams.

Single Frequency Array — Increment/Decrement Balance — Watch how a single frequency array tracks the balance between characters in s and t. Increments for s, decrements for t — if everything balances to zero, the strings are anagrams.

Algorithm

If the lengths of s and t differ, return false immediately.
Create a frequency array count of size 26, initialized to all zeros.
Iterate through both strings simultaneously (index 0 to n-1):
- Increment count[s[i] - 'a'] (deposit for s)
- Decrement count[t[i] - 'a'] (withdrawal for t)
After processing all characters, scan the count array:
- If any value is not zero, return false — the character frequencies differ.
If every value is zero, return true — the strings are valid anagrams.

Code

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

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) {
            return false;
        }
        
        vector<int> count(26, 0);
        
        for (int i = 0; i < s.length(); i++) {
            count[s[i] - 'a']++;
            count[t[i] - 'a']--;
        }
        
        for (int val : count) {
            if (val != 0) {
                return false;
            }
        }
        
        return true;
    }
};

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        
        count = [0] * 26
        
        for i in range(len(s)):
            count[ord(s[i]) - ord('a')] += 1
            count[ord(t[i]) - ord('a')] -= 1
        
        for val in count:
            if val != 0:
                return False
        
        return True

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        
        int[] count = new int[26];
        
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
            count[t.charAt(i) - 'a']--;
        }
        
        for (int val : count) {
            if (val != 0) {
                return false;
            }
        }
        
        return true;
    }
}

Complexity Analysis

Time Complexity: O(n)

We make a single pass through both strings (O(n) iterations), and then one pass through the 26-element frequency array (O(26) = O(1)). Total time: O(n), where n is the length of the strings.

Space Complexity: O(1)

The frequency array has a fixed size of 26 regardless of input length. This is constant space. Unlike the hash map approach, there is zero overhead for hashing or collision resolution — just direct array indexing, which is the fastest possible lookup.

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Valid Anagram

Description

Examples

Example 1

Example 2

Example 3

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Better Approach - Hash Map Frequency Count

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Single Frequency Array

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis