The O(n) Club: Valid Anagram, or How to Make Your Strings Get Along Without Therapy

The O(n) Club: Valid Anagram, or How to Make Your Strings Get Along Without Therapy

⚡ TL;DR

Quick test: Are "listen" and "silent" cosmic twins or just casual acquaintances? Either sort and compare, or do a fast character frequency check. Sorting is classic; counting is slick:

// Java: Sorting Approach
char[] a1 = s.toCharArray();
char[] a2 = t.toCharArray();
Arrays.sort(a1);
Arrays.sort(a2);
return Arrays.equals(a1, a2);

🧠 How Devs Usually Mess This Up

If you want to see smart people cry, watch them:

• Forget that ‘a’ and ‘A’ are as similar as Batman and batman (hint: not the same guy)
• Ignore the fate of spaces and punctuation (does “rat!” match “tar!” or are we in grammar prison?)
• Skip checking for empty strings (which are, weirdly, anagrams of themselves… thanks, programming gods)
• Sort strings without checking the lengths first. Have fun with false positives!
• Write a double for-loop solution, thus adding runtime smacks and possibly new gray hairs

🔍 What’s Actually Going On

Imagine your strings are two buckets of Scrabble tiles. An anagram means you can pour them out and every single tile matches — nothing left over, no stowaways under the table, not even that one dog-eared ‘Q’. Sorting both buckets and lining them up is a reliable way, but a bit slow. Counting is faster: tally up each tile from one bucket, subtract as you go through the other, and if everything totals zero, you’re golden. If not, someone’s been pocketing tiles when you weren’t looking.

🛠️ PseudoCode

• Step 1: Check Lengths
  

  if (s.length() != t.length()) return false;

  If they’re not the same size, don’t bother rearranging the deck chairs.

• Step 2: Count Letters (Lowercase A-Z Special)
  

  int[] count = new int[26];

  Pretend you’re playing with just 26 lettered blocks.

• Step 3: Count & Increment for s, Decrement for t
  

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

  This is where the ledger magic happens.

• Step 4: Make Sure You Broke Even
  

  for (int val : count) if (val != 0) return false;

  If someone still owes you a letter, not an anagram.

• Step 5: Success
  

  If you got here, congrats. Interviewer might even nod approvingly.

💻 The Code

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] count = new int[26]; // Only works for 'a'-'z', so don’t show off with emojis
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;
        count[t.charAt(i) - 'a']--;
    }
    for (int val : count) {
        if (val != 0) return false;
    }
    return true;
}

// Got Unicode, mixed case, or punctuation? Use a HashMap<Character, Integer> instead. Just don’t resent the question too loudly.

⚠️ Pitfalls, Traps & Runtime Smacks

• Case Confusion: ‘E’ vs ‘e’ — they might sound the same in your head, but not in your code.
• Spaces and Punctuation: “an a gram” is not “anagram” unless you squash the whitespace. Confirm requirements or prepare for disappointment.
• Empty Strings: Both empty? Well congratulations, you’ve found the world’s quietest anagram.
• Unicode or Non-English: If Unicode walks in, int[26] will burst into flames. Bring a map for those.
• Complexity:
  • Sorting: O(n log n) — respectable, not flashy
  • Frequency Counting: O(n) time and O(1) space (for a-z) — sweet spot for interviews

🧠 Interviewer Brain-Tattoo

Valid Anagram: the only time in coding when you can turn chaos into order with a few counters—or just alphabetize everything and hope nobody asks follow-up Unicode questions.