Logo

Kode$word

Valid Anagram – Frequency Counting Pattern Explained (LeetCode 242)
Valid Anagram – Frequency Counting Pattern Explained (LeetCode 242)

Valid Anagram – Frequency Counting Pattern Explained (LeetCode 242)

Using HashMap and Array Optimization to Detect Anagrams Efficiently

22 views
0
0
HashMapStringFrequency CountArraysLeetCodeEasy
Github icon

🔗 Problem Link

LeetCode 242 – Valid Anagram

👉 https://leetcode.com/problems/valid-anagram/

Introduction

This is one of the most important string frequency problems in coding interviews.

The idea of checking whether two strings are anagrams appears in many variations:

  1. Group Anagrams
  2. Ransom Note
  3. Find the Difference
  4. Permutation in String

If you master this pattern, you unlock a whole category of problems.

Let’s break it down step by step.

📌 Problem Understanding

Two strings are anagrams if:

  1. They contain the same characters
  2. With the same frequencies
  3. Order does not matter

Example 1

Input: s = "anagram"
t = "nagaram"
Output: true

Both contain:

a → 3
n → 1
g → 1
r → 1
m → 1

Example 2

Input: s = "rat"
t = "car"
Output: false

Different character frequencies.

🧠 Intuition

The core idea:

If two strings are anagrams, their character frequencies must match exactly.

So we:

  1. Check if lengths are equal.
  2. Count frequency of characters in first string.
  3. Subtract frequencies using second string.
  4. If at any point frequency becomes negative → not anagram.

💻 Your Code

class Solution {
public boolean isAnagram(String s, String t) {
if(s.length() != t.length()) return false;

HashMap<Character,Integer> mp = new HashMap<>();

for(int i =0;i<s.length();i++){
mp.put(s.charAt(i),mp.getOrDefault(s.charAt(i),0)+1);
}

for(int i =0; i < t.length();i++){
if(mp.containsKey(t.charAt(i)) && mp.get(t.charAt(i)) > 0){
mp.put(t.charAt(i),mp.get(t.charAt(i))-1);
}else{
return false;
}
}
return true;
}
}

🔍 Step-by-Step Explanation

1️⃣ Length Check

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

If lengths differ → cannot be anagrams.

2️⃣ Build Frequency Map

mp.put(s.charAt(i), mp.getOrDefault(s.charAt(i), 0) + 1);

Count occurrences of each character in s.

3️⃣ Subtract Using Second String

if(mp.containsKey(t.charAt(i)) && mp.get(t.charAt(i)) > 0)

If character exists and frequency is available → reduce it.

Otherwise → return false immediately.

🎯 Why This Works

We treat:

  1. First string as frequency builder
  2. Second string as frequency consumer

If all frequencies match perfectly, we return true.

⏱ Complexity Analysis

Time Complexity: O(n)

  1. One pass to build map
  2. One pass to compare

Space Complexity: O(26) ≈ O(1)

Only lowercase English letters allowed.

🔥 Optimized Approach – Using Array Instead of HashMap

Since the problem guarantees:

s and t consist of lowercase English letters

We can replace HashMap with an integer array of size 26.

This is faster and cleaner.

Optimized Version

class Solution {
public boolean isAnagram(String s, String t) {
if(s.length() != t.length()) return false;

int[] freq = new int[26];

for(char c : s.toCharArray()){
freq[c - 'a']++;
}

for(char c : t.toCharArray()){
freq[c - 'a']--;
if(freq[c - 'a'] < 0){
return false;
}
}

return true;
}
}

🚀 Why This Is Better

  1. No HashMap overhead
  2. Direct index access
  3. Cleaner code
  4. Faster in interviews

🏁 Final Thoughts

This problem teaches:

  1. Frequency counting pattern
  2. Early exit optimization
  3. Using arrays instead of HashMap when character set is limited
  4. Thinking in terms of resource balance

Valid Anagram is a foundation problem.

Once you master it, you can easily solve:

  1. Ransom Note
  2. Find the Difference
  3. Group Anagrams
  4. Check Equal Character Occurrences

Related Articles

Ransom Note – Frequency Counting Made Simple (LeetCode 383)

Ransom Note – Frequency Counting Made Simple (LeetCode 383)

Using HashMap to Validate Character Availability Efficiently

Read Article
Find the Difference – Smart ASCII Sum Trick (LeetCode 389)

Find the Difference – Smart ASCII Sum Trick (LeetCode 389)

Solving the Problem Using Character Arithmetic Instead of Extra Space

Read Article
Check if All Characters Have Equal Number of Occurrences – Frequency Map Approach (LeetCode 1941)

Check if All Characters Have Equal Number of Occurrences – Frequency Map Approach (LeetCode 1941)

Simple HashMap Technique to Validate Equal Character Frequencies

Read Article
Longest Palindrome – Building the Maximum Length from Given Letters (LeetCode 409)

Longest Palindrome – Building the Maximum Length from Given Letters (LeetCode 409)

Using Frequency Counting to Construct the Largest Possible Palindrome

Read Article

Ai Assistant Kas