In this post, we are going to solve the Minimum Window Substring Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.
Problem
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.
A substring is a contiguous sequence of characters within the string.
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.
Constraints:
m == s.lengthn == t.length1 <= m, n <= 105sandtconsist of uppercase and lowercase English letters.
Follow up: Could you find an algorithm that runs in O(m + n) time?
Now, let’s see the leetcode solution of Minimum Window Substring Leetcode Solution.
Minimum Window Substring Leetcode Solution in Python
class Solution:
def minWindow(self, s: str, t: str) -> str:
count = Counter(t)
required = len(t)
bestLeft = -1
minLength = len(s) + 1
l = 0
for r, c in enumerate(s):
count[c] -= 1
if count[c] >= 0:
required -= 1
while required == 0:
if r - l + 1 < minLength:
bestLeft = l
minLength = r - l + 1
count[s[l]] += 1
if count[s[l]] > 0:
required += 1
l += 1
return '' if bestLeft == -1 else s[bestLeft: bestLeft + minLength]
Minimum Window Substring Leetcode Solution in CPP
class Solution {
public:
string minWindow(string s, string t) {
vector<int> count(128);
int required = t.length();
int bestLeft = -1;
int minLength = s.length() + 1;
for (const char c : t)
++count[c];
for (int l = 0, r = 0; r < s.length(); ++r) {
if (--count[s[r]] >= 0)
--required;
while (required == 0) {
if (r - l + 1 < minLength) {
bestLeft = l;
minLength = r - l + 1;
}
if (++count[s[l++]] > 0)
++required;
}
}
return bestLeft == -1 ? "" : s.substr(bestLeft, minLength);
}
};
Minimum Window Substring Leetcode Solution in Java
class Solution {
public String minWindow(String s, String t) {
int[] count = new int[128];
int required = t.length();
int bestLeft = -1;
int minLength = s.length() + 1;
for (final char c : t.toCharArray())
++count[c];
for (int l = 0, r = 0; r < s.length(); ++r) {
if (--count[s.charAt(r)] >= 0)
--required;
while (required == 0) {
if (r - l + 1 < minLength) {
bestLeft = l;
minLength = r - l + 1;
}
if (++count[s.charAt(l++)] > 0)
++required;
}
}
return bestLeft == -1 ? "" : s.substring(bestLeft, bestLeft + minLength);
}
}
Note: This problem Minimum Window Substring is generated by Leetcode but the solution is provided by Chase2learn This tutorial is only for Educational and Learning purposes.
