Skip to content

048 — Permutation in String

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 2 revisions

48 — Permutation in String

LeetCode 567 · Medium. Given two strings s1 and s2, return true if s2 contains a permutation of s1 as a contiguous substring — that is, one of s1's character rearrangements appears somewhere in s2.

🍽️ Intuition

Think of s1 as a fixed hand of cards — say, three A's and two B's — and s2 as a long shelf of cards you're scanning past through a window exactly as wide as your hand. You don't care about the order the cards appear in inside the window, only whether the window currently holds exactly the same multiset of cards as your hand. So instead of comparing strings character by character (which cares about order), you compare frequency fingerprints — a count of each letter — and slide the window one card at a time, checking after every slide whether the fingerprints match.

🚩 Pattern-Recognition Cue

"Permutation of s1" appearing as a substring of s2 combines two of Sliding Window's strongest signals at once: a fixed window size (exactly s1.count, since a permutation can't change length) and an anagram/permutation-of-a-substring check, which always means comparing character-frequency state rather than re-sorting or re-comparing substrings directly.

🐢 Brute Force

At every possible window position in s2, build a fresh frequency count of that window from scratch and compare it against s1's frequency count.

func checkInclusionBruteForce(_ s1: String, _ s2: String) -> Bool {
    let s1Chars = Array(s1)
    let s2Chars = Array(s2)
    let n1 = s1Chars.count
    let n2 = s2Chars.count
    guard n1 <= n2 else { return false }

    let aVal = Character("a").asciiValue!
    var s1Counts = [Int](repeating: 0, count: 26)
    for c in s1Chars {
        s1Counts[Int(c.asciiValue! - aVal)] += 1
    }

    for start in 0...(n2 - n1) {
        var windowCounts = [Int](repeating: 0, count: 26)
        for i in start..<(start + n1) {
            windowCounts[Int(s2Chars[i].asciiValue! - aVal)] += 1
        }
        if windowCounts == s1Counts {
            return true
        }
    }

    return false
}

Big-O: O(n · m) time, where n = s2.count and m = s1.count — every one of the n - m + 1 window positions rebuilds its 26-slot count from scratch. O(1) extra space (fixed 26-slot arrays).

🚀 Optimal

Build the initial window's frequency count once, then slide one character at a time: add the incoming character, remove the outgoing one, and compare fingerprints — no rebuilding from scratch.

func checkInclusion(_ s1: String, _ s2: String) -> Bool {
    let s1Chars = Array(s1)
    let s2Chars = Array(s2)
    let n1 = s1Chars.count
    let n2 = s2Chars.count
    guard n1 <= n2 else { return false }

    let aVal = Character("a").asciiValue!
    var s1Counts = [Int](repeating: 0, count: 26)
    var windowCounts = [Int](repeating: 0, count: 26)

    for i in 0..<n1 {
        s1Counts[Int(s1Chars[i].asciiValue! - aVal)] += 1
        windowCounts[Int(s2Chars[i].asciiValue! - aVal)] += 1
    }

    if windowCounts == s1Counts {
        return true
    }

    for right in n1..<n2 {
        let addIndex = Int(s2Chars[right].asciiValue! - aVal)
        windowCounts[addIndex] += 1

        let removeIndex = Int(s2Chars[right - n1].asciiValue! - aVal)
        windowCounts[removeIndex] -= 1

        if windowCounts == s1Counts {
            return true
        }
    }

    return false
}

// smoke test
print(checkInclusion("ab", "eidbaooo"))   // true  ("ba" at index 3)
print(checkInclusion("ab", "eidboaoo"))   // false

Big-O: O(n) time — the initial window costs O(m), and each of the remaining n - m slides does O(1) work to update counts plus an O(26) (constant) array comparison. O(1) extra space — two fixed 26-slot arrays.

🔑 The Key Insight

The brute force treats each window position as an independent problem, throwing away all the counting work it just did the moment it moves to the next position. But a window sliding by one position only changes by exactly two characters: one leaves on the left, one enters on the right — everything else inside the window is untouched. Updating the frequency count incrementally (decrement the outgoing letter, increment the incoming one) captures that entire change in O(1), instead of paying O(m) to rebuild the whole fingerprint. That's what collapses O(n · m) down to O(n).

🔗 Related Chapters

  • Sliding Window — the fixed-size window sliding one step at a time, updating state incrementally rather than recomputing.
  • Arrays & Strings — the strings being scanned.
  • Hash Maps & Hash Sets — the character-frequency fingerprint, here a fixed 26-slot array standing in for a hash map keyed by letter.

🧸 Memory Sentence

Permutation in String is comparing card-hand fingerprints through a fixed-width window — slide one card at a time, update the count, and check if the hand matches.

✅ Check Your Understanding

The optimal solution compares two 26-element arrays (windowCounts == s1Counts) at every single slide, which looks like it should cost O(26) work every time — yet the overall algorithm is still described as O(n). Explain why treating that O(26) comparison as O(1) is valid here, and why it would stop being valid if the alphabet size weren't fixed (say, if the strings could contain any Unicode character).

⬅️ Previous: Longest Repeating Character Replacement · Next: Minimum Window Substring ➡️

Clone this wiki locally