Algorithm
Problem Name: 76. Minimum Window Substring
problem Link: https://leetcode.com/problems/minimum-window-substring/
Given two strings s and t of lengths m and n respectively, return the minimum window substring (A substring is a contiguous non-empty sequence of characters within a string.) 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.
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?
Code Examples
#1 Code Example with C Programming
Code -
C Programming
char* minWindow(char* s, char* t) {
int n = 0, cnt[128] = { 0 };
int head, tail, start, len = -1;
char c, *p;
if (!s || !*s || !t || !*t) return NULL;
while (c = *(t ++)) {
cnt[c] ++;
n ++; // total number of characters in T
}
head = tail = 0;
while (c = s[tail ++]) {
if (cnt[c] > 0) n --; // decrease total number if a valid character is found
cnt[c] --; // decrease count of current character
while (n == 0) { // all characters are found
if (len == -1 || len > tail - head) {
start = head;
len = tail - head;
}
c = s[head ++]; // advance head
cnt[c] ++; // increase count
if (cnt[c] > 0) {
n = 1; // a valid character was pushed out of head, will find it back from tail
}
}
}
if (len != -1) {
p = &s[start];
p[len] = 0;
} else {
p = "";
}
return p;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
string minWindow(string s, string t) {
unordered_mapm;
int i = 0, j = 0, count = 0, minLen = INT_MAX;
string res = "";
for(auto x: t) m[x]++, count++;
while(j < s.size()){
if(m[s[j++]]-- > 0) count--;
if(count == 0){
while(m[s[i]] < 0) m[s[i++]]++;
int len = j - i;
if(len < minLen){
minLen = len;
res = s.substr(i, len>;
}
m[s[i++]]++;
count++;
}
}
return res;
}
};
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public String minWindow(String s1, String s2) {
String window = "";
int j = 0;
int minLength = s1.length() + 1;
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) == s2.charAt(j)) {
j++;
if (j == s2.length()) {
int end = i + 1;
j--;
while (j >= 0) {
if (s1.charAt(i) == s2.charAt(j)) {
j--;
}
i--;
}
j++;
i++;
if (end - i < minLength) {
minLength = end - i;
window = s1.substring(i, end);
}
}
}
}
return window;
}
}
Input
Output
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const minWindow = function(s, t) {
const map = {}
for (const c of t) {
map[c] = (map[c] || 0) + 1
}
let counter = t.length
let start = 0
let end = 0
let minLen = Infinity
let minStart = 0
while (end < s.length) {
const eChar = s[end]
if (map[eChar] > 0) {
counter--
}
map[eChar] = (map[eChar] || 0) - 1
end++
while (counter === 0) {
if (end - start < minLen) {
minStart = start
minLen = end - start
}
const sChar = s[start]
map[sChar] = (map[sChar] || 0) + 1
if (map[sChar] > 0) {
counter++
}
start++
}
}
if (minLen !== Infinity) {
return s.substring(minStart, minStart + minLen)
}
return ''
}
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def minWindow(self, s, t):
cnt_s, cnt_t, n, left, r = {}, {}, len(s), set(t), -1
for c in t:
cnt_t[c] = cnt_t.get(c, 0) + 1
L = l = 0
while left:
r += 1
if r >= n:
return ""
cnt_s[s[r]] = cnt_s.get(s[r], 0) + 1
if s[r] in cnt_t and cnt_s[s[r]] == cnt_t[s[r]]:
left.discard(s[r])
R = r
cnt_s[s[r]] -= 1
while l < r < n:
cnt_s[s[r]] = cnt_s.get(s[r], 0) + 1
while s[l] not in cnt_t or cnt_s[s[l]] > cnt_t[s[l]]:
cnt_s[s[l]] -= 1
l += 1
if r - l < R - L:
L, R = l, r
r += 1
return s[L: R + 1]
Input
Output
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _076_MinimumWindowSubstring
{
public string MinWindow(string s, string t)
{
if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t) || t.Length > s.Length) { return string.Empty; }
var counts = new int[256];
foreach (var ch in t)
counts[ch]++;
var remaining = t.Length;
int left = 0, right = 0, minStart = 0, minLength = int.MaxValue;
while (right < s.Length)
{
if (--counts[s[right++]] >= 0) remaining--;
while (remaining == 0)
{
if (right - left < minLength)
{
minLength = right - left;
minStart = left;
}
if (++counts[s[left++]] > 0) remaining++;
}
if (minLength == t.Length)
break;
}
return minLength == int.MaxValue ? string.Empty : s.Substring(minStart, minLength);
}
}
}
Input
Output