Minimum Window Substring

This page explains Java solution to problem Minimum Window Substring using Sliding window.

Problem Statement

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Solution

package com.vc.hard;

import java.util.*;

class MinimumWindowSubstring {
    public String minWindow(String s, String t) {
        if(s == null || t == null) return "";

        HashMap<Character, Integer> map = new HashMap<>();
        for(int i = 0; i < t.length(); i++) {
            char ch = t.charAt(i);
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }

        int start = 0;
        int end = 0;
        int required = t.length();
        int minLength = Integer.MAX_VALUE;
        int minStart = 0;
        while(end < s.length()) {
            char ch = s.charAt(end);
            if(map.containsKey(ch)) {
                if(map.get(ch) > 0) required--;
                map.put(ch, map.get(ch) - 1);
                while(required == 0) {
                    if(minLength > end - start) {
                        minLength = end - start + 1;
                        minStart = start;
                    }
                    char c = s.charAt(start);
                    if(map.containsKey(c)) {
                        map.put(c, map.getOrDefault(c, 0) + 1);
                        if(map.get(c) > 0) required++;
                    }
                    start++;
                }
            }
            end++;
        }
        return minLength == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLength);
    }
}

Time Complexity

O(N + M) Where
N is total number of elements in an input search string.
M is total number of elements in an input string which needs to be searched.

Space Complexity

O(M) Where
M is total number of elements in an input string which needs to be searched.