Blind 75Easy

Valid Anagram — Frequency Comparison

Count character frequencies in both strings and ensure the counts match exactly.

Hash MapString

View problem on LeetCode

Problem Statement

Determine if two strings are anagrams of each other.

Why This Problem Matters

Reinforces frequency counting patterns.
Simple question testing ability to implement efficient counting.
Serves as basis for grouping anagrams and other string problems.

Thought Process

Check lengths first

Different lengths cannot be anagrams; early exit saves work.

Count letters

Use int[26] for lowercase letters or HashMap for general unicode.

Ensure counts return to zero

Increment for s, decrement for t; any negative count indicates mismatch.

Step-by-Step Reasoning

If lengths differ return false.
Initialise counts[26] to zero.
For each index i, counts[s[i]-'a']++ and counts[t[i]-'a']--.
Ensure all counts zero at end.

Dry Run

s = "anagram", t = "nagaram"

Counts cancel to zero; return true.

s = "rat", t = "car"

Counts differ; return false.

Complexity Analysis

Time

O(n)

Space

O(1)

Why

Fixed-size array for alphabet; linear scan.

Annotated Solution

JAVA

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

    int[] counts = new int[26];
    for (int i = 0; i < s.length(); i += 1) {
      counts[s.charAt(i) - 'a'] += 1;
      counts[t.charAt(i) - 'a'] -= 1;
    }

    for (int count : counts) {
      if (count != 0) {
        return false;
      }
    }
    return true;
  }
}

Counting differences in a fixed-size array keeps runtime linear with constant extra space.

Common Pitfalls

Ignoring length check wastes time on obvious mismatches.
Using HashMap unnecessarily for lowercase letters increases overhead.
Forgetting to check for negative counts mid-loop misses early failure opportunities.

Follow-Up Questions

How do you handle Unicode strings? (Use HashMap or int array sized to charset.)
Can you generalise to ignoring non-letter characters or case?

Key Takeaways

Frequency counters are a go-to tool for string comparison.

Always mention alphabet assumptions when choosing data structures.

Anagram logic extends naturally to grouping tasks.