Valid Anagram Problem in DSA (String + Hashing)

Introduction

The Valid Anagram problem is a very common DSA interview question based on strings and hashing. It is often asked whether a candidate can compare characters efficiently.

In simple words, this problem asks you to check whether two strings are anagrams of each other or not.

What is an Anagram?

An anagram is formed when two strings contain exactly the same characters with the same frequency, but the order of characters can be different.

This means:

Both strings must have the same length
Each character must appear the same number of times in both strings

Examples of Anagrams

"listen" and "silent"
"rat" and "tar"
"evil" and "vile"

Not Anagrams

"hello" and "world"
"cat" and "car"

What is the Valid Anagram Problem?

You are given two strings s and t. Your task is to check whether t is an anagram of s.

Example

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

Explanation

Both strings contain the same characters with the same frequency, so they are valid anagrams.

Brute Force Approach (Simple but Inefficient)

A basic approach is to sort both strings and then compare them.

Problems with Brute Force

Sorting takes extra time
Time Complexity becomes O(n log n)

While this approach works, interviews usually expect a better solution.

Optimized Approach Using Hashing

The most efficient way to solve this problem is by using Hashing.

Key Idea

Count the frequency of each character in both strings
Compare the counts
If all counts match, the strings are anagrams

This avoids sorting and improves performance.

Step-by-Step Explanation

Steps:

If lengths of both strings are different, return false
Create a frequency map for characters
Traverse the first string and increase character count
Traverse the second string and decrease character count
If any count becomes negative, return false
If all checks pass, return true

Dry Run Example

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

Character	Count After s	Count After t
a	3	0
n	1	0
g	1	0
r	1	0
m	1	0

All counts become zero, so strings are anagrams.

Code Implementation

C++ Code

bool isAnagram(string s, string t) {
    if (s.length() != t.length()) return false;

    unordered_map<char, int> count;

    for (char c : s) count[c]++;
    for (char c : t) {
        count[c]--;
        if (count[c] < 0) return false;
    }
    return true;
}

Java Code

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

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

    for (char c : s.toCharArray())
        map.put(c, map.getOrDefault(c, 0) + 1);

    for (char c : t.toCharArray()) {
        if (!map.containsKey(c) || map.get(c) == 0)
            return false;
        map.put(c, map.get(c) - 1);
    }
    return true;
}

Python Code

def isAnagram(s, t):
    if len(s) != len(t):
        return False

    count = {}

    for ch in s:
        count[ch] = count.get(ch, 0) + 1

    for ch in t:
        if ch not in count or count[ch] == 0:
            return False
        count[ch] -= 1

    return True

Time and Space Complexity

Time Complexity: O(n)
Space Complexity: O(n)

This solution is fast and interview-friendly.

Edge Cases to Consider

Empty strings
Strings with different lengths
Strings with special characters

Testing these cases ensures correctness.

Common Interview Variations

Check anagram ignoring case
Check anagram with spaces
Count number of anagram pairs

Most string-hashing problems are based on this logic.

Summary

The Valid Anagram problem is a basic yet important DSA question that helps you understand how hashing works with strings. By counting character frequencies instead of sorting, you can solve this problem efficiently in linear time. Mastering this approach will make it easier to handle many string comparison problems in coding interviews.