Skip to main content
DSA patterns

Permutation in String

mediumSliding windowCloudflareFastlyCisco

Problem statement

You are given two strings, s1 and s2. Return true if some rearrangement of s1's letters — a permutation of s1 — appears as a contiguous chunk inside s2, and false otherwise.

In other words: is there a window in s2, the same length as s1, that uses exactly the same letters as s1, the same number of times each, just possibly in a different order?

Examples

Example 1

Input: s1 = "ab", s2 = "eidbaooo"

Output: true

Explanation: s2 contains one permutation of s1, the substring "ba",

Example 2

Input: s1 = "ab", s2 = "eidboaoo"

Output: false

Explanation: No two-letter window of s2 uses exactly one a and one

Hints

Hint 1: A permutation of s1 inside s2 just means: some window of s2, the same length as s1, uses exactly the same letters, the same number of times each — order doesn't matter.

Approach

Optimal: Sliding window with counts maintained incrementally

Intuition

Between one window and the very next one, almost nothing changes: the leftmost letter leaves, one new letter joins on the right, and every other count stays exactly the same. Rebuilding the whole window from scratch, like Better does, throws away and redoes that unchanged work every single step. Instead, keep one running count array and just update it — subtract the letter that's leaving, add the letter that's arriving — then compare it to need. That turns the O(m) rebuild into an O(1) update, which is what makes this approach linear instead of O(n · m).

Steps

  1. If s2 is shorter than s1, return false. Let m = len(s1).
  2. Build need, a 26-slot count of the letters in s1.
  3. Build window, a 26-slot count of the first m characters of s2.
  4. If window already equals need, return true.
  5. For each index i from m to len(s2) - 1:
    • Add s2[i] to window — the letter entering on the right.
    • Remove s2[i - m] from window — the letter leaving on the left.
    • If window equals need, return true.
  6. If nothing matched by the end, return false.

Dry run

s1 = "ab" (so m = 2, need = {a: 1, b: 1}), s2 = "eidbaooo"

step window before letter added (right) letter removed (left) window after matches need?
build — s2[0..1] = "ei" — {e:1, i:1} no
i=2 {e:1, i:1} s2[2] = 'd' s2[0] = 'e' {i:1, d:1} no
i=3 {i:1, d:1} s2[3] = 'b' s2[1] = 'i' {d:1, b:1} no
i=4 {d:1, b:1} s2[4] = 'a' s2[2] = 'd' {a:1, b:1} yes → return true

The window itself moves "ei" → "id" → "db" → "ba" across s2, and "ba" at the last step is exactly the permutation of "ab" the example points to.

Edge cases: if s1 is longer than s2, step 1 catches it before any counting happens. If s1 has a repeated letter (like "aab"), the count comparison still works correctly, since it checks exact counts per letter, not just which letters are present.

flowchart LR A[Count s1's letters, and the first window of s2] --> B{Do the two count arrays match?} B -- yes --> C[Found a permutation - return true] B -- no --> D[Add the letter entering on the right] D --> E[Remove the letter leaving on the left] E --> B

Complexity

Time O(n) - the window slides forward one letter at a time. At each step, exactly one letter leaves and one enters, so updating the counts is O(1); comparing two 26-length arrays is O(26), a constant. There are about `n` slides in total, so the whole scan is O(n).

Space O(1) - the same two fixed 26-slot count arrays as Better.

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        m, n = len(s1), len(s2)
        if m > n:
            return False

        need = [0] * 26
        window = [0] * 26
        for ch in s1:
            need[ord(ch) - ord('a')] += 1
        for ch in s2[:m]:
            window[ord(ch) - ord('a')] += 1

        if window == need:
            return True

        for i in range(m, n):
            window[ord(s2[i]) - ord('a')] += 1
            window[ord(s2[i - m]) - ord('a')] -= 1
            if window == need:
                return True
        return False


if __name__ == "__main__":
    print(str(Solution().checkInclusion("ab", "eidbaooo")).lower())  # true
    print(str(Solution().checkInclusion("ab", "eidboaoo")).lower())  # false
RecapThe whole problem in a few lines, for the night before
  • Spot it: does s2 contain any permutation of s1 as a substring
  • Idea: fixed window of length len(s1) over s2 with letter counts; if the window counts equal s1's counts, return true
  • Cost: O(n) time, O(1) space (26 letters)
  • Trap: the window must be contiguous and exactly len(s1) long; it is not a subsequence

Interview follow-ups

  • Return the starting index of the first matching window instead of true / false.

    Track the index instead of returning a boolean: return 0 when the very first window (built before the loop) matches, and return i - m + 1 when a later window matches inside the loop, since i is the index of the letter that just entered on the right. Return -1 if the loop finishes with no match. Same O(n) time.

  • Find every starting index where a permutation of s1 occurs, not just the first.

    Don't return as soon as one match is found — instead, append its starting index to a results list and keep sliding the window all the way to the end of s2. The time complexity stays O(n), since the window still only takes one O(1) step per position; only the amount of output can grow.

  • What if the strings could contain uppercase letters or characters beyond a–z?

    Swap the fixed 26-slot arrays for a hash map keyed by character, and keep the exact same sliding logic — add the entering character, remove the leaving one, compare the two maps. The time complexity stays O(n), but a hash map lookup is O(1) only on average, unlike a fixed-size array's guaranteed O(1).

Frequently asked questions

Because that's what a permutation is: a rearrangement of the same letters. Two strings use the same letters the same number of times if and only if one can be reordered into the other. So once the counts match exactly, the order inside the window is irrelevant — some arrangement of s1 is sitting right there.

The question asks whether a permutation of s1 — meaning a string the exact same length as s1 — shows up inside s2. Every window checked is exactly len(s1) characters long, since a shorter or longer window could never be a rearrangement of s1. That's also why the function returns false immediately when s1 is longer than s2: no window of that size can even exist.

The same shape shows up when you need an exact multiset match inside a stream — for example, checking whether a fixed set of required resource tags (say, two gpu allocations and one ssd) ever appears together in a contiguous stretch of a longer allocation log, regardless of the order they were requested in.

All three slide a window across a string and keep small letter counts, but the rule for "is this window good?" is different each time. Here, the window must match s1's counts exactly. Longest Repeating Character Replacement allows a window to be close enough — off by at most k changes. Longest Substring Without Repeating Characters asks for no letter to repeat at all, with no fixed target to match against.