Minimum Window Substring - LeetCode Daily Challenge

Problem Statement

Given two strings s and t of lengths m and n respectively, return the minimum window 

substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

Example 1

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Try here before watching the video.

Video Solution

Java Code

class Solution {
    public String minWindow(String s, String t) {
        
        int windowStart = 0, minLength = Integer.MAX_VALUE, matched = 0, start = 0;
        Map<Character, Integer> tMap = new HashMap<>();

        for(char ch : t.toCharArray()) {
            tMap.put(ch, tMap.getOrDefault(ch, 0) + 1);
        }

        for(int windowEnd = 0; windowEnd < s.length(); windowEnd++) {
            char currChar = s.charAt(windowEnd);
            if(tMap.containsKey(currChar)) {
                tMap.put(currChar, tMap.get(currChar) - 1);
                if(tMap.get(currChar) >= 0) {
                    matched += 1;
                }
            }

            while(matched == t.length()) {
                if(minLength > (windowEnd - windowStart + 1)) {
                    minLength = windowEnd - windowStart + 1;
                    start = windowStart;
                }

                char leftChar = s.charAt(windowStart);
                windowStart += 1;

                if(tMap.containsKey(leftChar)) {
                    if(tMap.get(leftChar) == 0) {
                        matched -= 1;
                    }
                    tMap.put(leftChar, tMap.get(leftChar) + 1);
                }
            }
        }

        if(minLength > s.length()) {
            return "";
        }
        return s.substring(start, start + minLength);
    }
}

C++ Code

class Solution {
public:
    string minWindow(string s, string t) {
        int windowStart = 0, minLength = INT_MAX, matched = 0, start = 0;
        unordered_map<char, int> tMap;

        for (char ch : t) {
            tMap[ch] += 1;
        }

        for (int windowEnd = 0; windowEnd < s.length(); windowEnd++) {
            char currChar = s[windowEnd];
            if (tMap.find(currChar) != tMap.end()) {
                tMap[currChar] -= 1;
                if (tMap[currChar] >= 0) {
                    matched += 1;
                }
            }

            while (matched == t.length()) {
                if (minLength > (windowEnd - windowStart + 1)) {
                    minLength = windowEnd - windowStart + 1;
                    start = windowStart;
                }

                char leftChar = s[windowStart];
                windowStart += 1;

                if (tMap.find(leftChar) != tMap.end()) {
                    if (tMap[leftChar] == 0) {
                        matched -= 1;
                    }
                    tMap[leftChar] += 1;
                }
            }
        }

        if (minLength > s.length()) {
            return "";
        }
        return s.substr(start, minLength);
    }
};

Python Code

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        window_start = 0
        min_length = float('inf')
        matched = 0
        start = 0
        t_map = {}

        for ch in t:
            t_map[ch] = t_map.get(ch, 0) + 1

        for window_end in range(len(s)):
            curr_char = s[window_end]
            if curr_char in t_map:
                t_map[curr_char] -= 1
                if t_map[curr_char] >= 0:
                    matched += 1

            while matched == len(t):
                if min_length > (window_end - window_start + 1):
                    min_length = window_end - window_start + 1
                    start = window_start

                left_char = s[window_start]
                window_start += 1

                if left_char in t_map:
                    if t_map[left_char] == 0:
                        matched -= 1
                    t_map[left_char] += 1

        return "" if min_length > len(s) else s[start:start + min_length]

Javascript Code

var minWindow = function(s, t) {
    let windowStart = 0, minLength = Infinity, matched = 0, start = 0;
    const tMap = {};

    for (const ch of t) {
        tMap[ch] = (tMap[ch] || 0) + 1;
    }

    for (let windowEnd = 0; windowEnd < s.length; windowEnd++) {
        const currChar = s[windowEnd];
        if (tMap.hasOwnProperty(currChar)) {
            tMap[currChar] -= 1;
            if (tMap[currChar] >= 0) {
                matched += 1;
            }
        }

        while (matched === t.length) {
            if (minLength > windowEnd - windowStart + 1) {
                minLength = windowEnd - windowStart + 1;
                start = windowStart;
            }

            const leftChar = s[windowStart];
            windowStart += 1;

            if (tMap.hasOwnProperty(leftChar)) {
                if (tMap[leftChar] === 0) {
                    matched -= 1;
                }
                tMap[leftChar] += 1;
            }
        }
    }

    return minLength > s.length ? "" : s.substring(start, start + minLength);
};

Go Code

func minWindow(s string, t string) string {
	windowStart, minLength, matched, start := 0, len(s)+1, 0, 0
	tMap := make(map[byte]int)

	for _, ch := range t {
		tMap[byte(ch)]++
	}

	for windowEnd := 0; windowEnd < len(s); windowEnd++ {
		currChar := s[windowEnd]
		if _, exists := tMap[currChar]; exists {
			tMap[currChar]--
			if tMap[currChar] >= 0 {
				matched++
			}
		}

		for matched == len(t) {
			if minLength > (windowEnd - windowStart + 1) {
				minLength = windowEnd - windowStart + 1
				start = windowStart
			}

			leftChar := s[windowStart]
			windowStart++

			if _, exists := tMap[leftChar]; exists {
				if tMap[leftChar] == 0 {
					matched--
				}
				tMap[leftChar]++
			}
		}
	}

	if minLength > len(s) {
		return ""
	}
	return s[start : start+minLength]
}

Complexity Analysis

Time Complexity: O(M + N), where M is the length of string s and N is the length of string t.
Space Complexity: O(1), as we are using a map formed by the characters of string which can hold max 26 characters.