Solving a Hard Sliding Window Problem (Step-by-Step Breakdown)

prasanth cherukuri — Mon, 09 Mar 2026 07:20:59 +0000

Hard Sliding Window Pattern – Minimum Window Substring (Thinking Process)

Problem Description: Given two strings s and p. Find the smallest substring in s consisting of all the characters (including duplicates) of the string p. Return empty string in case no such substring is present. If there are multiple such substring of the same length found, return the one with the least starting index.

A brute force method of checking all substrings is obviously very expensive.

1. Initial Thought

Since we are dealing with continuous substrings, I immediately started thinking in terms of two pointers / sliding window technique.

2. Core Requirement

For each window, we need to check whether it contains all the target characters including duplicates.

3. Expensive Check (Naive Approach)

An easy way to check this is:

Create an array/map with character → frequency of the target string
For every window, check if the window contains all required characters with the required frequency

But this check becomes expensive if done repeatedly.

4. Key Idea

Instead of checking the frequency array repeatedly, we modify the frequency array while traversing the window.

At any point in time:

freq > 0 → we still need more of that character
freq = 0 → requirement for that character is satisfied
freq < 0 → the window already contains extra occurrences of that character

5. How to Remove the Expensive Check

To avoid repeated comparisons, we introduce a count variable.

Steps:

Initialize count = length of target string
Reduce the frequency of characters while expanding the window
Reduce the count only if the frequency of that character was positive

When count becomes 0, it means the current window contains all required characters.

6. Shrinking the Window

But we are not done yet — the current window might still be shrinkable.

Steps:

Move the left pointer
Increment the frequency of that character
If the frequency becomes positive, it means we removed a required character
Set count = 1 and stop shrinking

At each valid stage, keep track of:

Minimum length subarray
Start index of that subarray

7. Final Step

Return the smallest valid subarray found.

Key Optimisations

Instead of repeatedly comparing frequency arrays, we maintain a single integer count
The frequency array naturally handles both relevant and irrelevant characters
We only care about characters that belong to the target string

A useful observation:

Irrelevant characters will never make the frequency positive, so they don't affect the validity check.

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Forem: prasanth cherukuri