Last updated on October 9th, 2024 at 10:02 pm

Here, We see Minimum Window Substring LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Minimum Window Substring LeetCode Solution

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.

1. Minimum Window Substring Leetcode Solution 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 "";
    }
};

2. Minimum Window Substring Leetcode Solution 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. Minimum Window Substring Leetcode Solution 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;    
};

4. Minimum Window Substring Leetcode Solution 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]