Permutation In String

MEDIUM✓ CHIP-TIMEDLC #567 — FULL STATEMENT ↗

The drill: Somewhere inside the longer string there may be a contiguous block whose letters are exactly the first string, shuffled. Order can't identify such a block — only letter counts can, checked across every window of the right width.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A short pattern string and a longer search string arrive together, and the question is whether some contiguous block of the search string is exactly a rearrangement of the pattern's letters.

Order inside that block never has to match the pattern's own order — only the multiset of letters and their counts need to line up exactly; position for position within the block doesn't matter.

The block, if one exists, must be exactly as wide as the pattern itself; wider or narrower stretches never qualify no matter what letters they contain.

EX 01

s1 = "ab" · s2 = "oobao"

→ true

THE SCRAMBLE SITS MID-STRING

EX 02

s1 = "ab" · s2 = "ooboo"

→ false

RIGHT LETTERS NEVER ADJACENT

EX 03

s1 = "abc" · s2 = "cba"

→ true

WHOLE HAYSTACK IS THE PERMUTATION

pattern length stays small while the search string runs up to around ten thousand characters
both strings contain only lowercase English letters
a matching block must be exactly as wide as the pattern
the result reported is a boolean, not the matching block itself

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A permutation match ignores order entirely. What fingerprint of a block of text survives any shuffle of it?

HINT 2 THE STRUCTURE

Every candidate window has the same width as the pattern, so this is a fixed-size window over 26 letter counts — the question is how to avoid recounting per slide.

HINT 3 ONE STEP FROM THE ANSWER

Roll the window: one letter enters, one leaves, two count cells change. Track how many of the 26 cells agree with the pattern; a match is all 26 agreeing at once.

COACH'S BOARD — THE PATTERN, STEP BY STEP

ROLLING THE 26 COUNTSPATTERN · SLIDING WINDOW — FIXED WIDTHs1 = "ab" · s2 = "oobao"

LETTER TALLIES (need · have) · MATCHES

— empty —

STEP 1

Pattern "ab" needs one a and one b. Slide a width-2 window across "oobao" and count how many of the letter tallies agree.

STEP 1 / 5 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/permutation-in-string.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        m, n = len(s1), len(s2)
        if m > n:
            return False
        a = ord("a")
        need = [0] * 26
        have = [0] * 26
        for c in s1:
            need[ord(c) - a] += 1
        for c in s2[:m]:
            have[ord(c) - a] += 1
        matches = sum(1 for i in range(26) if need[i] == have[i])
        if matches == 26:
            return True
        for right in range(m, n):
            enter = ord(s2[right]) - a
            have[enter] += 1
            if have[enter] == need[enter]:
                matches += 1            # this cell just came into agreement
            elif have[enter] == need[enter] + 1:
                matches -= 1            # this cell just fell out of agreement
            leave = ord(s2[right - m]) - a
            have[leave] -= 1
            if have[leave] == need[leave]:
                matches += 1
            elif have[leave] == need[leave] - 1:
                matches -= 1
            if matches == 26:
                return True
        return False

TIME O(N)SPACE O(26)PYTHON · RACE PACE · 31 LN

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        m = len(s1)
        key = sorted(s1)  # canonical form of the pattern
        for i in range(len(s2) - m + 1):
            if sorted(s2[i:i + m]) == key:
                return True
        return False

TIME O(N·M LOG M)SPACE O(M)PYTHON · TRAINING PACE · 8 LN

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        if (m > n) return false;
        int[] need = new int[26];
        int[] have = new int[26];
        for (char c : s1.toCharArray()) need[c - 'a']++;
        for (int i = 0; i < m; i++) have[s2.charAt(i) - 'a']++;
        int matches = 0;
        for (int i = 0; i < 26; i++) {
            if (need[i] == have[i]) matches++;
        }
        if (matches == 26) return true;
        for (int right = m; right < n; right++) {
            int enter = s2.charAt(right) - 'a';
            have[enter]++;
            if (have[enter] == need[enter]) matches++;        // came into agreement
            else if (have[enter] == need[enter] + 1) matches--; // fell out of agreement
            int leave = s2.charAt(right - m) - 'a';
            have[leave]--;
            if (have[leave] == need[leave]) matches++;
            else if (have[leave] == need[leave] - 1) matches--;
            if (matches == 26) return true;
        }
        return false;
    }
}

TIME O(N)SPACE O(26)JAVA · RACE PACE · 27 LN

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int m = s1.length();
        char[] key = s1.toCharArray(); // canonical form of the pattern
        Arrays.sort(key);
        for (int i = 0; i + m <= s2.length(); i++) {
            char[] window = s2.substring(i, i + m).toCharArray();
            Arrays.sort(window);
            if (Arrays.equals(window, key)) {
                return true;
            }
        }
        return false;
    }
}

TIME O(N·M LOG M)SPACE O(M)JAVA · TRAINING PACE · 15 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED