Coding interview problems › Sliding Window

🪟 Sliding Window Medium

Permutation in String

Permutation in String explained: slide a fixed window of len(s1) over s2 and compare letter counts in O(n). Anagram-in-window trick, tested Python, live visual.

Also searched as: check if string contains permutation of another · find anagram substring sliding window

🪟

Try it live Free

Sliding Window

Slide a window of fixed size and update it with one entering and one leaving element per step. Here the window holds letter counts instead of a sum.

Also useful: Hash Tables

Open the playground →

The problem

Given two strings s1 and s2, return True if some contiguous substring of s2 is a rearrangement (permutation) of s1.

Inputs1 = "ab", s2 = "eidbaooo"
OutputTrue

"ba" is in s2.

Inputs1 = "ab", s2 = "eidboaoo"
OutputFalse

The key insight

A permutation of s1 is any string with the same letter counts and the same length. So slide a window of exactly len(s1) over s2, keeping its letter counts up to date by adding the entering letter and removing the leaving one, and check whether the counts match.

Brute force first: Generating every permutation of s1 is factorial; sorting each window is O(n · m log m).

Step-by-step approach

  1. If len(s1) > len(s2), return False.
  2. Build counts for s1 and for the first window of s2.
  3. If they match, return True.
  4. Slide the window one step: add s2[i], remove s2[i - m], and compare again.
  5. Return False if no window matched.

Python solution

PYTHON 3tested
def check_inclusion(s1, s2):
    m = len(s1)
    if m > len(s2):
        return False
    need = [0] * 26
    win = [0] * 26
    for ch in s1:
        need[ord(ch) - 97] += 1
    for i, ch in enumerate(s2):
        win[ord(ch) - 97] += 1             # letter entering
        if i >= m:
            win[ord(s2[i - m]) - 97] -= 1  # letter leaving
        if win == need:
            return True
    return False

Complexity

TimeO(26 · n)
SpaceO(1)

Each step does O(1) count updates plus a 26-element comparison, so it is linear in len(s2). A matches counter can make each step O(1).

Common mistakes

Frequently asked questions

What is the time and space complexity of Permutation in String?

O(26 · n), effectively O(n), where n is the length of s2, and O(1) space for two 26-letter count arrays.

How do I find all starting indices of anagrams instead?

Use the same window, but instead of returning True, append i - m + 1 every time the counts match.

Can I avoid comparing all 26 counts each step?

Yes. Keep a count of how many letters currently have matching counts, and update it only for the entering and leaving letters.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Sliding Window Sliding Window lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.