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)
Top comments (0)