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:

1. If lengths of both strings are different, return false

2. Create a frequency map for characters

3. Traverse the first string and increase character count

4. Traverse the second string and decrease character count

5. If any count becomes negative, return false

6. 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.