Sliding Window

Minimum Window Substring

Rajeev SinghAlgorithms1 mins read

Minimum Window Substring

Problem Statement

Given two strings s and t, find the smallest substring of s that has all the characters of t (including duplicates). If there is no such substring, then return an empty string.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The smallest substring of s that includes all the characters of t is "BANC".

Example 2:

Input: s = "a", t = "a"
Output: "a"t

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the smallest substring. Since no such substring exists, return "".

Solution

This problem is based on the variable-size sliding window pattern. We can use the sliding window strategy similar to the one discussed in the problem Longest Substring with K distinct characters.

Here is the complete implementation with comments for clarity:

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

class MinimumWindowSubstring {    
    private static String findMinimumWindowSubstring(String s, String t) {
        int n = s.length();
        
        // length of the minimum window substring (smallest substring of s that has all characters of t)
        int minWindowSubstrLength = Integer.MAX_VALUE;

        // start index of the minimum window substring
        int minWindowSubstrStart = 0;

        // stores the count of each character in the current window
        Map<Character, Integer> windowCharMap = new HashMap<>();

        // stores the count of each character in the string t
        Map<Character, Integer> substrMap = new HashMap<>();

        for(int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            substrMap.put(c, substrMap.getOrDefault(c, 0)+1);
        }
        
        int windowStart = 0;
        for(int windowEnd = 0; windowEnd < n; windowEnd++) {
            // Add the next character of the string to the window
            char c = s.charAt(windowEnd);
            windowCharMap.put(c, windowCharMap.getOrDefault(c, 0)+1);
            
            // Keep looking for a smaller window while the current window substring contains all the characters of t
            while(containsAll(windowCharMap, substrMap)) {
                if(windowEnd-windowStart+1 < minWindowSubstrLength) {
                    minWindowSubstrLength = windowEnd-windowStart+1;
                    minWindowSubstrStart = windowStart;
                }

                // move the leftmost character out of the window
                char leftChar = s.charAt(windowStart);
                windowCharMap.put(leftChar, windowCharMap.get(leftChar)-1);
                if(windowCharMap.get(leftChar) == 0) {
                    windowCharMap.remove(leftChar);
                }
                windowStart++; // shrink the window
            }
        }
        
        return s.substring(minWindowSubstrStart, minWindowSubstrStart+minWindowSubstrLength);
    }

    private static boolean containsAll(Map<Character, Integer> windowCharMap, Map<Character, Integer> substrMap) {
        for(Map.Entry<Character, Integer> entry : substrMap.entrySet()) {
            char c = entry.getKey();
            int count = entry.getValue();
            
            if(!windowCharMap.containsKey(c)) {
                return false;
            }
            
            if(windowCharMap.get(c) < count) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        String s = keyboard.next();
        String t  = keyboard.next();
        keyboard.close();
        
        System.out.printf("Minimum window substring = %s%n", findMinimumWindowSubstring(s, t));
    }
}