The O(n) Club: Find All Anagrams in a String: Java-Only, No Permutation Panic

The O(n) Club: Find All Anagrams in a String: Java-Only, No Permutation Panic

⚡ TL;DR

You get a pattern. You get a string. Find every place that pattern shows up, scrambled—but only if the letters are neighbors. Don’t brute-force every possible arrangement unless you like slow computers and sadness.

// Inefficient: for those who like to hear fan noise
for (int i = 0; i <= s.length() - p.length(); i++) {
    if (isAnagram(s.substring(i, i + p.length()), p)) result.add(i);
}
// isAnagram() = sort and compare, or tally frequencies

🧠 How Devs Usually Mess This Up

Raise your hand if you started by generating every permutation of the pattern and looking for them all in the string? Yep, that’s a textbook invitation for timeouts and existential crisis.
Others mix up the rules and snatch letters from scattered positions instead of sticking to good old-fashioned substringing. Or, they start with off-by-one windows and discover not every bug is a feature.

🔍 What’s Actually Going On

Imagine your brain is a warehouse worker paws-deep in bins of socks. You’re hunting for any set of bins, all lined up, that contain the exact types and numbers of socks as your favorite set—never mind the order. That, friends, is sliding window meets frequency counting. Pick a window the size of your pattern. Shuffle in a new item on the right, eject the old leftmost sock, and compare counts like a suspicious customs officer. If the frequencies match? You found an anagram party.

🛠️ PseudoCode

• Count each character in the pattern:
  

  int[] pCount = new int[26]; // For a-z only

• Initialize a window count for the string:
  

  int[] sCount = new int[26];

• Collect the first window’s character counts:
  

  for (int i = 0; i < p.length(); i++) sCount[s.charAt(i)-'a']++;

• If the window matches the pattern, log index 0. Now slide:
  

  for (int i = p.length(); i < s.length(); i++) {
      sCount[s.charAt(i)-'a']++;   // Add rightmost
      sCount[s.charAt(i-p.length())-'a']--; // Remove leftmost
      if (Arrays.equals(sCount, pCount)) result.add(i-p.length()+1);
  }

• Return your hard-earned list of starting indices.

💻 The Code

import java.util.*;
 public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s == null || p == null || s.length() < p.length()) return result;
        int[] pCount = new int[26];
        int[] sCount = new int[26];
        for (int i = 0; i < p.length(); i++) {
            pCount[p.charAt(i)-'a']++;
            sCount[s.charAt(i)-'a']++;
        }
        if (Arrays.equals(pCount, sCount)) result.add(0);
        for (int i = p.length(); i < s.length(); i++) {
            sCount[s.charAt(i)-'a']++;
            sCount[s.charAt(i-p.length())-'a']--;
            if (Arrays.equals(pCount, sCount)) result.add(i-p.length()+1);
        }
        return result;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Try this with s.length() < p.length() and your list should be as empty as your patience after four hours of LeetCode.
• Using HashMap instead of arrays for a-z? That’s like replacing a chef with a robot for toast. More code, same results, more bugs.
• Off-by-one errors: The classic “window slides off the rails” syndrome.
• Time: O(n) because you only loop through the string like a disciplined adult. Space: O(1)—we just tally 26 possible letters.

🧠 Interviewer Brain-Tattoo

Remember: If you’re thinking ‘generate every permutation’, your interviewer is thinking ‘next candidate, please’. Sliding window. Always sliding window.