Sliding Window Approach for Minimum Window Substring: Algorithm and Implementation

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, 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:

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, 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 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.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}