Introduction

The Valid Anagram problem involves checking whether two strings contain the same characters with the same frequencies.

Two strings are called anagrams if:

  • both strings contain identical characters
  • character frequencies are same
  • order may differ

Given two strings:

  • s
  • t

the task is to determine whether they are anagrams.

This problem helps in understanding:

  • hashing
  • frequency counting
  • sorting techniques
  • string comparison 

Example

Input:s = "listen"
t = "silent"

Output:
True

Explanation:
Both strings contain:
l,i,s,t,e,n
with same frequencies.

Input:
s = "hello"
t = "world"

Output:
False

Explanation:
Character frequencies are different.

Constraints

 1 <= s.length, t.length <= 5 * 10^4s and t contain lowercase English letters

Approach 1 : Brute Force

Explanation

The simplest way to solve this problem is:

  1. Compare frequency of every character manually
  2. Ensure frequencies match in both strings

This approach works but repeated counting increases time complexity.

Steps

  1. Check string lengths.
  2. Traverse characters of first string.
  3. Count frequency in both strings.
  4. If frequencies differ:
    • return false
  5. Otherwise:
    • return true

Dry Run

Input:s = "listen"
t = "silent"

Check character l:
Frequency in s = 1
Frequency in t = 1

Check character i:
Frequency matches

Continue traversal...

All frequencies match

Final Result:
True

Brute Force Code

Complexity Analysis

Time Complexity: O(n²)Explanation:
Frequencies are repeatedly counted.

Space Complexity: O(1)
Explanation:
No extra data structures are used.

Approach 2 : Better Solution (Sorting)

Explanation

If two strings are anagrams:

  • their sorted forms become identical

The idea is:

  1. Sort both strings
  2. Compare sorted strings

This reduces repeated frequency counting.

Steps

  1. Check string lengths.
  2. Sort first string.
  3. Sort second string.
  4. Compare sorted strings.
  5. Return result.

Dry Run

Input:s = "listen"
t = "silent"

Sort strings:
"listen" → "eilnst"
"silent" → "eilnst"

Compare:
Both are equal

Final Result:
True

Better Code

Complexity Analysis

Time Complexity: O(n log n)Explanation:
Sorting is performed on both strings.

Space Complexity: O(n)
Explanation:
Extra space may be used during sorting.

Approach 3 : Optimized Solution (Hashing)

Explanation

The optimized solution uses frequency counting.

The idea is:

  1. Count frequencies of characters
  2. Compare frequencies

If frequencies match:

  • strings are anagrams

This provides:

  • O(n) time complexity

Steps

  1. Check string lengths.
  2. Create frequency hashmap.
  3. Increment frequency using first string.
  4. Decrement frequency using second string.
  5. Check all frequencies become 0.

Dry Run

Input:s = "listen"
t = "silent"

Store frequencies:
l → +1
i → +1
s → +1
t → +1
e → +1
n → +1

Process second string:
s → -1
i → -1
l → -1
e → -1
n → -1
t → -1
All frequencies become 0

Final Result:
True

Optimized Code

Complexity Analysis

Time Complexity: O(n)Explanation:
Each character is processed once.

Space Complexity: O(n)
Explanation:
Extra hashmap is used for frequencies.

Edge Cases

  1. Strings have different lengths
  2. Strings contain repeated characters
  3. Strings contain one character
  4. Strings already equal
  5. Strings contain special characters

Why This Problem is Important

This problem helps in understanding:

  1. Hashing
  2. Frequency counting
  3. Sorting techniques
  4. String comparison
  5. Optimized traversal

It is one of the most important string hashing interview problems.

Real-World Applications

Anagram concepts are used in:

  1. Search engines
  2. Spell checking systems
  3. NLP systems
  4. Pattern matching
  5. Data grouping systems

Common Mistakes

  1. Forgetting length check
  2. Incorrect hashmap updates
  3. Sorting wrong strings
  4. Frequency mismatch handling

Interview Tips

Interviewers often expect:

  1. Hashing optimization
  2. Frequency counting logic
  3. O(n) solution explanation

Always explain why equal frequencies guarantee an anagram.

Related Questions

  1. Group Anagrams
  2. Palindrome
  3. Character Frequency
  4. Ransom Note
  5. First Unique Character

Final Takeaway

The Valid Anagram problem is a fundamental hashing problem that teaches frequency counting and optimized string comparison techniques. Understanding this problem builds a strong foundation for advanced hashing and string processing interview problems.