The O(n) Club: Permutation in String — Where Brute Force Goes To Die

The O(n) Club: Permutation in String — Where Brute Force Goes To Die

⚡ TL;DR

Given two strings, does s2 have a substring that’s a permutation of s1? Please, step away from generating all permutations (unless you hate yourself). Sliding window + counting is your best friend:

// Java hot-take:
boolean checkInclusion(String s1, String s2) {
    // Count the letters of s1, slide a window over s2
}

🧠 How Devs Usually Mess This Up

Ah, the classic: generating all permutations of s1 and searching for them in s2. If that’s your go-to, may your CPU rest in peace. Spoiler: “abc” has only 6 permutations, but “abcdefgh” has 40,320. That’s almost as many regrets as lines of spaghetti code in your legacy project. Also, folks love confusing substrings (must be consecutive!) with subsequences (which are basically ninja letters teleporting around). Don’t be that dev.

🔍 What’s Actually Going On

Picture s1 as a highly suspicious grocery list, and you want to see if any block of s2 (with the same length) matches your list, order doesn’t matter. No shuffling, no swapping, just matching baskets. Here’s the trick: use two arrays of 26 (because nobody is asking for Unicode Sudoku), one for s1, one for the current window in s2. Slide that window through s2 and look for a perfect match. Boom — no factorials required, just some good old frequency matching.

🛠️ PseudoCode

• Make a count array for s1.
  int[] s1Count = new int[26];
  Count every character in s1.
• Set up the first window in s2.
  int[] s2Count = new int[26];
  Count the first s1.length() chars in s2.
• Slide the window along s2:
  • Compare s1Count and s2Count. If match: you win.
  • Else, remove the leftmost char and add the next rightmost.
  • Repeat until done (don’t skip the very last window — rookie mistake!).
• Return true if you get a match. If not, at least you tried.

💻 The Code

public boolean checkInclusion(String s1, String s2) {
    if (s1.length() > s2.length()) return false;
    int[] s1Count = new int[26];
    int[] s2Count = new int[26];
    for (int i = 0; i < s1.length(); i++) {
        s1Count[s1.charAt(i) - 'a']++;
        s2Count[s2.charAt(i) - 'a']++;
    }
    int matches = 0;
    for (int i = 0; i < 26; i++) {
        if (s1Count[i] == s2Count[i]) matches++;
    }
    int left = 0;
    for (int right = s1.length(); right < s2.length(); right++) {
        if (matches == 26) return true;
        int idxIn = s2.charAt(right) - 'a';
        int idxOut = s2.charAt(left++) - 'a';
        s2Count[idxIn]++;
        if (s2Count[idxIn] == s1Count[idxIn]) matches++;
        else if (s2Count[idxIn] == s1Count[idxIn] + 1) matches--;
        s2Count[idxOut]--;
        if (s2Count[idxOut] == s1Count[idxOut]) matches++;
        else if (s2Count[idxOut] == s1Count[idxOut] - 1) matches--;
    }
    return matches == 26;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Substring means consecutive — not “anywhere in s2” and not “skip-around-anagram bingo”.
• If s1 is longer than s2, don’t waste precious cycles — return false first.
• Don’t forget to check the last window after the loop! (Off-by-one errors send more code to production hell than anything else.)
• Performance: O(N) time (where N = s2.length). Space? Two arrays, 26 each. A bargain for this much efficiency.

🧠 Interviewer Brain-Tattoo

When interviewers say permutation and substring in one breath, just smile and reach for your frequency arrays. Leave the factorials to math club after school.