In this article, we will learn to resolve the Minimum Window Substring problem by using Sliding Window algorithm

Problem

  • Given two strings s of length m and t of length n

  • Find a minimum substring in s which contains all characters in t

Example

  • Input: given two strings aaaaaaaaaaaabbbbbcdd and abcdd

  • Expected output: abbbbbcdd

Approach: Sliding Window

Iterating over s window by window with two index pointers i and j to find the minimum substring

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

public class WindowSliding_GivenString_FindMinSubstr {  
    public static String findMinSubstr(String s, String t) {
        Map<Character, Integer> tChars = new HashMap<>();
        for(char c : t.toCharArray()) {
            tChars.compute(c, (key, value) -> value == null ? 1 : ++value);
        }

        Map<Character, Integer> sChars = new HashMap<>();
        String windowSubstr = "";
        String minSubstr = "";
        int i = 0;
        int j = 0;
        int matched = 0;

        while(i < s.length()) {
            Character c;
            while(j < s.length() && matched < tChars.size()) {
                c = s.charAt(j++);
                sChars.compute(c, (key, value) -> value == null ? 1 : ++value);
                windowSubstr += c;

                if (tChars.containsKey(c) && tChars.get(c).equals(sChars.get(c))) matched++;
            }

            if (matched == tChars.size() && (minSubstr.equals("") || windowSubstr.length() < minSubstr.length())){
                minSubstr = windowSubstr;
            }

            c = windowSubstr.charAt(0);
            sChars.compute(c, (key, value) -> --value);
            if (tChars.containsKey(c) && tChars.get(c) > sChars.get(c)) matched--;
            windowSubstr = windowSubstr.substring(1);
            i++;
        }

        return minSubstr;
    }

    public static void main(String[] args) {
        System.out.println(findMinSubstr("ADOBECODEBANC", "ABC"));
        System.out.println(findMinSubstr("aaaaaaaaaaaabbbbbcdd", "abcdd"));
    }
}

Output

BANC  
abbbbbcdd

Complexity

  • Time complexity: O(m+n)

  • Space complexity: O(m+n)

Algorithm