# Sliding Window Approach for Minimum Window Substring: Algorithm and Implementation

> Learn the sliding window approach for Minimum Window Substring. Discover an efficient O(n) algorithm to find the smallest substring containing all characters of T using two pointers and hashmaps.

- Repository: [Kevin Naughton Jr./interviews](https://github.com/kdn251/interviews)
- Tags: deep-dive
- Published: 2026-03-04

---

**The sliding window approach for Minimum Window Substring finds the smallest substring containing all characters of T by expanding and contracting a two-pointer window over S while tracking character frequencies in a hashmap, achieving O(n) time complexity.**

The Minimum Window Substring problem asks you to locate the minimum-length substring of string S that contains all characters from string T, including duplicates. This classic LeetCode challenge (problem 76) appears throughout the kdn251/interviews repository in multiple variants, all implementing the same efficient sliding window technique.

## How the Sliding Window Algorithm Works

The solution maintains two pointers, `start` and `end`, that define a mutable window over string S. A hashmap tracks how many of each required character remain to be found, while a `counter` variable monitors how many characters are still needed to satisfy the requirement.

### Phase 1: Expanding the Window

The algorithm first expands the window by advancing the `end` pointer from left to right across S. For each character `c1 = S.charAt(end)`, the implementation decrements its count in the frequency map. In [`leetcode/string/MinimumWindowSubstring.java`](https://github.com/kdn251/interviews/blob/main/leetcode/string/MinimumWindowSubstring.java), lines 37-41 handle this expansion:

- If the decremented count remains non-negative (meaning the character was still needed), the `counter` is decremented to indicate one less required character remains.

This phase continues until the window contains all necessary characters from T, indicated by `counter` reaching zero.

### Phase 2: Contracting the Window

Once the window becomes valid (`counter == 0`), the algorithm attempts to shrink it from the left to find a smaller valid substring. Lines 45-48 in the source file update the minimum window answer whenever a shorter valid window is discovered.

The contraction process involves moving the `start` pointer rightward:

- The character at `start` (`c2`) is added back to the hashmap (lines 50-52).
- If this addition causes the count to become positive again, the window no longer satisfies the requirement, and `counter` is incremented (lines 53-55).
- The contraction stops when the window becomes invalid, and the algorithm resumes expansion with the `end` pointer.

## HashMap Initialization and Edge Cases

Before the main loop begins, the implementation initializes the hashmap to contain every distinct character of S with a count of 0 (lines 14-18). It then loads the required frequencies from T into this map. Lines 20-25 contain an optimization that aborts early if T contains any character absent from S, preventing unnecessary computation.

## Time and Space Complexity

The sliding window approach achieves **O(n)** time complexity where n is the length of S, because both the `start` and `end` pointers traverse the string at most once. The space complexity is **O(k)** where k represents the number of distinct characters in the alphabet (typically the character set size of S), due to the hashmap storage requirements.

## Java Implementation Example

The following runnable example demonstrates how to invoke the sliding window solution as implemented in the repository:

```java
public class Demo {
    public static void main(String[] args) {
        MinimumWindowSubstring solver = new MinimumWindowSubstring();

        String s = "ADOBECODEBANC";
        String t = "ABC";

        // Expected output: "BANC"
        System.out.println(solver.minWindow(s, t));
    }
}

```

This code executes the sliding window algorithm defined in [`leetcode/string/MinimumWindowSubstring.java`](https://github.com/kdn251/interviews/blob/main/leetcode/string/MinimumWindowSubstring.java), printing the minimal window `"BANC"` for the sample input.

## Repository File Locations

The kdn251/interviews repository contains this sliding window implementation in multiple locations for interview preparation:

- **leetcode/string/MinimumWindowSubstring.java** – Primary implementation used for LeetCode practice
- **leetcode/hash-table/MinimumWindowSubstring.java** – Variant organized under hash-table category
- **company/facebook/MinimumWindowSubstring.java** – Facebook interview preparation version
- **company/linkedin/MinimumWindowSubstring.java** – LinkedIn interview preparation version  
- **company/uber/MinimumWindowSubstring.java** – Uber interview preparation version

All files contain identical core logic, demonstrating the reusability of the sliding window pattern across different company-specific interview contexts.

## Summary

- The sliding window approach uses two pointers (`start` and `end`) to dynamically expand and contract a window over string S.
- A hashmap tracks remaining required character frequencies from T, while a `counter` tracks how many characters are still needed.
- The algorithm runs in O(n) time because each pointer traverses S at most once, with O(k) space for the character map.
- The implementation spans multiple files in the kdn251/interviews repository, including [`leetcode/string/MinimumWindowSubstring.java`](https://github.com/kdn251/interviews/blob/main/leetcode/string/MinimumWindowSubstring.java) and company-specific variants.

## Frequently Asked Questions

### Why is the sliding window approach more efficient than checking all substrings?

**The sliding window approach achieves O(n) linear time because it visits each character at most twice**—once by the `end` pointer during expansion and once by the `start` pointer during contraction. A brute-force solution checking all possible substrings would require O(n²) time to examine every window and O(n) time to validate each one, resulting in O(n³) total complexity.

### How does the counter variable track valid windows?

**The `counter` decrements when the `end` pointer includes a character still needed from T, and increments when the `start` pointer removes a required character from a valid window.** When `counter` reaches zero, the current window contains all characters of T with sufficient frequency. This mechanism avoids expensive full-map comparisons on every iteration.

### What happens if string T contains characters not present in S?

**The algorithm detects this edge case during initialization (lines 20-25) and returns an empty string immediately.** By pre-loading all distinct characters from S into the hashmap with zero counts, the implementation can verify that every character in T exists in S before beginning the sliding window process.

### Can this sliding window technique handle Unicode characters?

**Yes, the algorithm works with any character set provided the hashmap implementation supports those characters.** The Java implementation uses `HashMap<Character, Integer>`, which supports Unicode characters. The space complexity remains O(k) where k is the number of distinct characters in the specific strings S and T, not the entire Unicode space.