Valid Anagram

Problem Statement

Given two strings s and t, determine whether t is an anagram of s.

Two strings are anagrams if they contain the same characters with the same frequencies.

---

Brute Force Intuition

In an interview, you can explain it like this:

Sort both strings. If the sorted strings are identical, then they are anagrams.

Sorting rearranges the characters into the same order.

Complexity

• Time Complexity: O(N log N)
• Space Complexity: O(1) (Ignoring sorting space)

Brute Force Code

class Solution {

    public boolean isAnagram(String s, String t) {

        if (s.length() != t.length())
            return false;

        char[] a = s.toCharArray();
        char[] b = t.toCharArray();

        Arrays.sort(a);
        Arrays.sort(b);

        return Arrays.equals(a, b);
    }
}

---

Moving Towards the Optimal Approach

Sorting is unnecessary.

We only need to know:

How many times
each character appears.

For lowercase English letters,

there are only:

26 Characters

Maintain a frequency array.

---

Pattern Recognition

Whenever you see:

• Same Characters
• Character Frequency
• Permutation Check

Think:

Frequency Counting

---

Key Observation

Increase frequency while traversing:

s

Decrease frequency while traversing:

t

If every frequency becomes:

0

the strings are anagrams.

---

Optimal Approach

Step 1

Create:

int[] freq = new int[26];

---

Step 2

Traverse both strings.

freq[s.charAt(i)-'a']++;

freq[t.charAt(i)-'a']--;

---

Step 3

If every frequency equals:

0

Return:

true

Otherwise:

false

---

Optimal Java Solution

class Solution {

    public boolean isAnagram(String s, String t) {

        if (s.length() != t.length())
            return false;

        int[] freq = new int[26];

        for (int i = 0; i < s.length(); i++) {

            freq[s.charAt(i) - 'a']++;

            freq[t.charAt(i) - 'a']--;
        }

        for (int count : freq) {

            if (count != 0)
                return false;
        }

        return true;
    }
}

---

Dry Run

Input

s = "anagram"

t = "nagaram"

Frequency after processing:

a → 0

n → 0

g → 0

r → 0

m → 0

All frequencies:

0

Answer:

true

---

Why Frequency Counting Works?

Both strings contribute equally to the frequency array.

If every increment is cancelled by a decrement,

both strings contain exactly the same characters.

---

Complexity Analysis

Metric	Complexity
Time Complexity	O(N)
Space Complexity	O(1)

---

Interview One-Liner

Count character frequencies in one string, subtract frequencies using the other string, and verify that every count becomes zero.

---

Pattern Learned

Character Frequency

↓

Count Array

↓

Compare Frequencies

Similar Problems

• Valid Anagram
• Group Anagrams
• Find All Anagrams in a String
• Ransom Note

---

Memory Trick

Think:

First String

↓

Increase Count

↓

Second String

↓

Decrease Count

↓

All Zero?

↓

Anagram

Mental Model

Count

↓

Cancel

↓

All Zero

↓

Valid

Whenever you hear:

"Check whether two strings are anagrams"

your brain should immediately think:

Frequency Array