Permutation in String

PracticeNeetCode ↗LeetCode ↗

Given two strings s1 and s2, return true if s2 contains a contiguous substring that is a permutation of s1.

Example

Key Pointers

• A permutation of s1 is just any arrangement with the same character counts — compare counts, not order.
• Slide a fixed-size window of length len(s1) across s2, comparing 26-letter count arrays instead of substrings.
• Rather than re-comparing all 26 counts on every slide, track how many of the 26 letters currently have matching counts, and update that number incrementally as one character leaves and one enters the window.

Step-by-Step Analysis

1. If s1 is longer than s2, return False immediately.
2. Build a count array need for s1, and a count array window for the first len(s1) characters of s2.
3. Count how many of the 26 letters already agree between need and window — call it matches.
4. Slide the window one character at a time: update matches for the character leaving, then for the character entering.
5. Whenever matches == 26, a permutation has been found — return True. If the window reaches the end without that, return False.

Complexity

Time: O(n) where n = len(s2) — Space: O(1)

Code

def checkInclusion(s1: str, s2: str) -> bool:
    if len(s1) > len(s2):
        return False

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

    for i in range(len(s1)):
        window[ord(s2[i]) - ord('a')] += 1

    matches = sum(1 for i in range(26) if need[i] == window[i])

    left = 0
    for right in range(len(s1), len(s2)):
        if matches == 26:
            return True

        add_ch = ord(s2[right]) - ord('a')
        window[add_ch] += 1
        if window[add_ch] == need[add_ch]:
            matches += 1
        elif window[add_ch] == need[add_ch] + 1:
            matches -= 1

        remove_ch = ord(s2[left]) - ord('a')
        window[remove_ch] -= 1
        if window[remove_ch] == need[remove_ch]:
            matches += 1
        elif window[remove_ch] == need[remove_ch] - 1:
            matches -= 1
        left += 1

    return matches == 26

Code Explanation

How the solution above works, piece by piece.

1. A permutation of s1 is any string with the same letter counts, so compare counts of a window the size of s1.
2. need holds the counts of s1; window the counts of the first len(s1) letters of s2.
3. matches = how many of the 26 letters currently have equal counts. 26 means the window is a permutation.
4. Sliding by one adds s2[right] and removes s2[left]. Only those two letters change, so matches is updated by ±1 each instead of recomparing all 26 counts.
5. Check matches == 26 at each step (and once more after the loop for the last window). O(n) time, O(26) space.

Visual Walkthrough

Running it on s1 = "ab", s2 = "eidbaooo":

Video Explanation

NeetCode — Permutation in String, LeetCode 567