Last updated on January 19th, 2025 at 10:41 pm

Here, we see a Minimum Window Substring LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Hash Table, Sliding Window, String, Two-Pointers

Companies

Facebook, LinkedIn, Snapchat, Uber

Level of Question

Hard

Minimum Window Substring LeetCode Solution

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

2. Coding Pattern Used in Solution

The provided code uses the Sliding Window pattern. This pattern is commonly used to solve problems involving contiguous subarrays or substrings. The idea is to maintain a “window” (a range of indices) that satisfies certain conditions, and then adjust the window dynamically to find the optimal solution.

3. Code Implementation in Different Languages

3.1 Minimum Window Substring C++

class Solution {
public:
    string minWindow(string s, string t) {
        int m=s.size(), n=t.size();
        unordered_map<char, int> mp;
        
        int ans = INT_MAX; 
        int start = 0; 
        
        for(auto x:t)
            mp[x]++;
        
        int count = mp.size();
        
        int i = 0, j = 0;

        while (j < s.length()) {
            mp[s[j]]--;
            if (mp[s[j]] == 0)
                count--;

            if (count == 0) {
                while (count == 0) {
                    if (ans > j - i + 1) {
                        ans = j - i + 1;
                        start = i;
                    }
                    mp[s[i]]++;
                    if (mp[s[i]] > 0)
                        count++;

                    i++;
                }
            }
            j++;
        }
        if (ans != INT_MAX)
            return s.substr(start, ans);
        else
            return "";
    }
};

3.2 Minimum Window Substring Java

class Solution {
    public String minWindow(String s, String t) {
    char[] needToFind = new char[256];
    char[] hasFound = new char[256];
    int sLen = s.length();
    int tLen = t.length();
    int count = 0;
    int optLen = Integer.MAX_VALUE; // opt stands for optimal
    int optBegin = 0;
    int optEnd = 0;
    for (int i = 0; i < tLen; i++) { // gives a counter for each character in t
      needToFind[t.charAt(i)]++;
    }
    for (int begin = 0, end = 0; end < sLen; end++) {
      if (needToFind[s.charAt(end)] == 0) { // skips irrelevant char
        continue;
      }
      char currEnd = s.charAt(end); // the char at the end
      hasFound[currEnd]++;
      if (hasFound[currEnd] <= needToFind[currEnd]) {
        count++;
      }
      if (count == tLen) { // pauses end, moves beginning to the right as much as possible
        char currBegin = s.charAt(begin); // char at begin
        while (hasFound[currBegin] > needToFind[currBegin] || needToFind[currBegin] == 0) {
          if (hasFound[currBegin] > needToFind[currBegin]) {
            hasFound[currBegin]--;
          }
          begin++;
          currBegin = s.charAt(begin);
        }
        if (optLen > end - begin + 1) { // if current length is smaller, update our optimum solution
          optLen = end - begin + 1;
          optBegin = begin;
          optEnd = end;
        }
      }
    }
    if (count != tLen) {
      return "";
    }
    return s.substring(optBegin, optEnd + 1);
  }        
}

3.3 Minimum Window Substring JavaScript

var minWindow = function(s, t) {
    let min = "", left = 0, right = -1;
    let map = {};
    t.split('').forEach(element => {
        if (map[element]==null) map[element] = 1;
        else map[element] = map[element] + 1;
    });
    let count = Object.keys(map).length;

    while (right <= s.length) {
        if (count == 0) {
            let current = s[left];
            if (map[current] != null) map[current]++;	
            if (map[current] > 0) count++;    
			
            let temp = s.substring(left, right+1)
            if (min == "") min = temp;
            else min = min.length<temp.length?min:temp;	
            left++;
        } else {
            right++;
            let current = s[right];
            if (map[current] != null) map[current]--;
			
            if (map[current] == 0) count--;
        }
    }
    return min;    
};

3.4 Minimum Window Substring Python

class Solution(object):
    def minWindow(self, s, t):
        need, missing = collections.Counter(t), len(t)
        i = I = J = 0
        for j, c in enumerate(s, 1):
            missing -= need[c] > 0
            need[c] -= 1
            if not missing:
                while i < j and need[s[i]] < 0:
                    need[s[i]] += 1
                    i += 1
                if not J or j - i <= J - I:
                    I, J = i, j
        return s[I:J]

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(m + n)	O(k)
Java	O(m + n)	O(k)
JavaScript	O(m + n)	O(k)
Python	O(m + n)	O(k)

where m is the length of s, n is the length of t, and k is the size of the character set.