Permutation in String

Interview Problem Interview Medium Fixed-size Window Array String

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.checkInclusion(s1, s2). The inputs contain lowercase English letters. Return whether s2 contains a substring that is a permutation of s1.

Starter code

class Solution:
    def checkInclusion(self, s1, s2):
        pass

Test cases

contains-ba

{
  "args": [
    "ab",
    "eidbaooo"
  ]
}

Expected: true

Wizard outline

Step 1: Initialize Solution.checkInclusion
Replace the empty starter with the first real state owned by Solution.checkInclusion. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Contains Ba case
Complete the readable core algorithm for one representative Interview case. Slide a window of len(s1) while updating character counts incrementally.
Step 4: Harden the Multiplicity boundary
Repair the reviewed boundary and pass the complete submission contract. The difference array is all zero exactly when the current fixed-length window and s1 have equal counts for every letter, which is precisely the definition of a permutation. Each slide updates it to represent the next window.

Footguns and prerequisites

A substring with all required distinct characters is insufficient; every multiplicity must match.
arrays strings two pointers sliding window
hashing and sets

Reviewed references

LeetCode 567 — Permutation in String

Practice prerequisites

Slide a Fixed Window(opens in a new tab)
Slide a Fixed Window isolates before appending a result, the rolling total contains exactly values[right - width + 1:right + 1]. That focused state discipline is required when implementing permutation in string as a complete Interview Problem.

Recommended approach and implementation

Build a 26-entry difference array by adding s1 counts and subtracting the first s2 window, then slide by restoring the outgoing character and subtracting the incoming character.

Why it works: The difference array is all zero exactly when the current fixed-length window and s1 have equal counts for every letter, which is precisely the definition of a permutation. Each slide updates it to represent the next window.

class Solution:
    def checkInclusion(self, s1, s2):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        width = len(s1)
        if width > len(s2):
            return False
        difference = [0] * 26
        for index in range(width):
            difference[ord(s1[index]) - 97] += 1
            difference[ord(s2[index]) - 97] -= 1
        if all(value == 0 for value in difference):
            return True
        for right in range(width, len(s2)):
            difference[ord(s2[right - width]) - 97] += 1
            difference[ord(s2[right]) - 97] -= 1
            if all(value == 0 for value in difference):
                return True
        return False

Similar exercises

Longest Repeating Character Replacement(opens in a new tab)