DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Permutation in String

mediumSliding window

Problem statement

Given two strings of lowercase letters, s1 and s2, return true if some rearrangement of s1 appears in s2 as a contiguous substring, and false otherwise. In other words: does s2 contain a block of len(s1) characters that uses exactly the same letters, with the same counts, as s1?

Examples

Example 1

Input: s1 = "ops", s2 = "devsopteam"

Output: true

Explanation: "sop" starts at index 3 and is a rearrangement of "ops".

Example 2

Input: s1 = "log", s2 = "glyco"

Output: false

Explanation: The three-letter blocks are "gly", "lyc" and "yco". None uses exactly l, o, g.

Hints

Approach

Keep 26-slot counts for s1 and for the current window of s2, plus matches: how many of the 26 letters currently have equal counts in both. The window is a rearrangement of s1 exactly when matches == 26.

  1. Count s1 and the first m letters of s2. Compute matches.
  2. Slide the window: for each letter entering or leaving, check whether that letter's count was equal before the change and whether it is equal after, and adjust matches by one.
  3. Return true as soon as matches == 26.

Each step touches two letters, so the scan is linear with no 26-array comparisons at all.

ComplexityTime O(n)Space O(1)
Python
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
m, n = len(s1), len(s2)
if m > n:
return False
need = [0] * 26
have = [0] * 26
for i in range(m):
need[ord(s1[i]) - 97] += 1
have[ord(s2[i]) - 97] += 1
matches = sum(need[c] == have[c] for c in range(26))
def change(c: int, delta: int) -> None:
nonlocal matches
if have[c] == need[c]:
matches -= 1 # this letter was balanced, now it won't be
have[c] += delta
if have[c] == need[c]:
matches += 1
for i in range(m, n):
if matches == 26:
return True
change(ord(s2[i]) - 97, +1) # entering
change(ord(s2[i - m]) - 97, -1) # leaving
return matches == 26

Follow-up questions

  • Return the start index of the first matching window instead of a boolean.
  • Support any characters, not just lowercase letters.

Frequently asked questions

It is the same window. Here you stop at the first match and return a boolean; there you collect every starting index.

The check at the top of the loop tests the window that ends just before index i. The final return tests the last window, which the loop never gets to check.

It is a clean test of the fixed-window counting pattern. The same technique detects whether some stretch of N consecutive events contains exactly an expected mix, for example a batch of log lines with one start, one ready and one stop event for a service.