LeetCode #242 - Valid Anagram

📝 Introduction

Given two strings, determine whether they are anagrams of each other.
Two strings are anagrams if they contain the same characters with the same frequencies, regardless of the order.

Constraints:

• Only uppercase letters (e.g., ‘A’ to ‘Z’) are considered.
• Strings must be the same length to qualify as anagrams.
• Output true if they are anagrams, otherwise false.

💡 Approach & Key Insights

• The core idea is to check whether the two strings contain the exact same characters with the same counts.
• If their lengths differ, they can’t be anagrams.
• There are multiple valid ways to compare character distributions:
  • Sort and compare
  • Count frequencies using a fixed-size array (best for character sets of known size)

🛠️ Breakdown of Approaches

1️⃣ Brute Force / Naive Approach — Sorting

• Explanation:
  Sort both strings and check if they are equal. If sorted versions are identical, then the strings are anagrams.

• Time Complexity: O(N log N) – Due to sorting of both strings.

• Space Complexity: O(1) – Assuming in-place sorting.

• Example/Dry Run:

1
Input: str1 = "INTEGER", str2 = "TEGERNI"
2
Step 1: Sort str1 → "EEGINRT"
3
Step 2: Sort str2 → "EEGINRT"
4
Step 3: Compare both → Equal → return true
5

6
Output: true

2️⃣ Optimized Approach — Frequency Count

• Explanation:
  Use a frequency array of size 26 (for uppercase letters).

  • Increment count for characters in str1
  • Decrement for characters in str2
  • If all frequencies are 0 in the end → anagrams

• Time Complexity: O(N) – One pass for each string.

• Space Complexity: O(1) – Fixed array size of 26.

• Example/Dry Run:

1
Input: str1 = "INTEGER", str2 = "TEGERNI"
2
Step 1: freq[] = [0,...,0]
3

4
Step 2: For str1 →
5
I+1, N+1, T+1, E+1, G+1, E+1, R+1
6
→ freq = {G:1, E:2, I:1, N:1, R:1, T:1}
7

8
Step 3: For str2 →
9
T-1, E-1, G-1, E-1, R-1, N-1, I-1
10
→ freq = all zero
11

12
Step 4: All frequencies are zero → return true
13

14
Output: true

3️⃣ Best / Final Optimized Approach

• Explanation:
  Frequency counting is optimal for limited character sets (like uppercase/lowercase letters).

  • No sorting
  • No additional data structures like maps or sets
  • Linear time and constant space

• Time Complexity: O(N)

• Space Complexity: O(1)

📊 Complexity Analysis

📉 Optimization Ideas

• Convert both strings to the same case (e.g., uppercase) to make comparison case-insensitive if needed.
• If dealing with Unicode characters, use a HashMap instead of fixed-size array.
• Early termination: While building the frequency array, if any count goes negative, return false early.

📌 Example Walkthroughs & Dry Runs

1
Example 1:
2
Input: str1 = "CAT", str2 = "ACT"
3

4
Step 1: freq[26] = {0}
5
Step 2: +1 for C, A, T → freq[C]=1, A=1, T=1
6
Step 3: -1 for A, C, T → all become 0
7
Output: true
8

9
Example 2:
10
Input: str1 = "RULES", str2 = "LESRT"
11

12
Step 1: freq[26] = {0}
13
Step 2: +1 for R, U, L, E, S → freq[R]=1, U=1, L=1, E=1, S=1
14
Step 3: -1 for L, E, S, R, T → freq[T]=-1 (unexpected char)
15
Output: false

🔗 Additional Resources

• GeeksforGeeks – Anagram Check

Author: Abdul Wahab
Date: 19/07/2025