Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/76.html
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.
Constraints:
m == s.length
n == t.length
1 <= m, n <= 105
s
andt
consist of uppercase and lowercase English letters.
Follow up: Could you find an algorithm that runs in O(m + n)
time?
Algorithm
The key to solving this problem is to efficiently move the left pointer when scanning a string. The variable i in the for loop can be considered equivalent to the right pointer.
-
To move the left pointer, find the first occurrence of the target character while ensuring that the count of this character is greater than the corresponding count in the target string.
-
When comparing the count of the target and count, it’s important to note that they may not be of the same length. For example, in the string “AAAABC”, count will be equal only when it reaches the character “C”, so it’s necessary to shrink the window before comparing with the current minimum length.
-
When moving the left pointer in the while loop, the condition
found[s.charAt(left)]> 1
should be replaced withfound[s.charAt(left)] > target[s.charAt(left)]
, because we need to check whether the current count of the character is greater than the corresponding count in the target string. -
To process the result, instead of keeping track of the position of the smallest window using two integers, it’s possible to use a string that is initially empty, and assign the smallest window to it at each iteration. This way, there is no need to check if the integers are negative to see if there is a result.
Code
-
public class Minimum_Window_Substring { public static void main(String[] args) { Minimum_Window_Substring out = new Minimum_Window_Substring(); Solution s = out.new Solution(); System.out.println(s.minWindow("ADOBECODEBANC", "ABC")); // output: "BANC" } public class Solution_easy_understand { public String minWindow(String s, String t) { if (s == null || t == null || s.length() == 0) { return ""; } // left,right pointing to window range int left = 0; // left int right = 0; // right int[] foundMap = new int[256]; // count of each char in this window range int[] targetMap = new int[256]; int countInRange = 0; int neededInRange = t.length(); int minSize = Integer.MAX_VALUE; String result = ""; // pre-process for (int i = 0; i < t.length(); i++) { char current = t.charAt(i); targetMap[current]++; } // start scanning while (right < s.length()) { char c = s.charAt(right); if (targetMap[c] > 0) { if (foundMap[c] < targetMap[c]) { countInRange++; } foundMap[c]++; // if all found in s, record window size if (countInRange == neededInRange) { // eg: "ADOBBECAODEBANNNNC" . when at 2nd "A", will enter this if, and do the shrink first, the check min while ( left < s.length() && ( targetMap[s.charAt(left)] == 0 // not in target[] || (targetMap[s.charAt(left)] > 0 && foundMap[s.charAt(left)] > targetMap[s.charAt(left)]) // more than needed in target[] ) ) { // @review: June-21-2016, "(targetMap[s.charAt(l)] > 0" NOT necessary, since statement before || is covering it foundMap[s.charAt(left)]--; // @note: no need to countInRange-1, since while condition ensured countInRange will always be equal to neededCharCount left++; } // check minSize, only after shrinking window if (right - left + 1 < minSize) { minSize = right - left + 1; result = s.substring(left, right + 1); } } } right++; } return result; } } class Solution { public String minWindow(String s, String t) { if (s == null || t == null || s.length() == 0) { return ""; } // left,right pointing to window range int left = 0; // left int right = 0; // right int[] countMap = new int[256]; // target chars needed for (char each : t.toCharArray()) { countMap[each]++; } int countInRange = 0; int minSize = Integer.MAX_VALUE; String result = ""; while (right < s.length()) { --countMap[s.charAt(right)]; if (countMap[s.charAt(right)] >= 0) { // @note: >= countInRange++; } while (countInRange == t.length()) { if (minSize > right - left + 1) { minSize = right - left + 1; result = s.substring(left, right + 1); } ++countMap[s.charAt(left)]; // '--' above if, so '++' back if (countMap[s.charAt(left)] > 0) { countInRange--; } left++; } right++; } return result; } } } ############ class Solution { public String minWindow(String s, String t) { Map<Character, Integer> mp = new HashMap<>(); int begin = 0, end = 0, counter = t.length(), minLen = Integer.MAX_VALUE, minStart = 0, size = s.length(); for (char c : s.toCharArray()) mp.put(c, 0); for (char c : t.toCharArray()) { if (mp.containsKey(c)) mp.put(c, mp.get(c) + 1); else return ""; } while (end < size) { if (mp.get(s.charAt(end)) > 0) counter--; mp.put(s.charAt(end), mp.get(s.charAt(end)) - 1); end++; while (counter == 0) { if (end - begin < minLen) { minStart = begin; minLen = end - begin; } mp.put(s.charAt(begin), mp.get(s.charAt(begin)) + 1); if (mp.get(s.charAt(begin)) > 0) { counter++; } begin++; } } if (minLen != Integer.MAX_VALUE) { return s.substring(minStart, minStart + minLen); } return ""; } } // class Solution { // public String minWindow(String s, String t) { // int[] count = new int['z' - 'A' + 1]; // int uniq = 0; // for (int i = 0; i < t.length(); ++i) { // if (++count[t.charAt(i) - 'A'] == 1) uniq++; // } // int found = 0,i = 0,j = 0; // int minLen = Integer.MAX_VALUE; // int minJ = Integer.MAX_VALUE; // while (found < uniq) { // while (i < s.length()) { // if (found >= uniq) break; // if (--count[s.charAt(i) - 'A'] == 0) found++; // i++; // } // if (found < uniq) break; // while (j < i && count[s.charAt(j) - 'A'] < 0) count[s.charAt(j++) - 'A']++; // if (i - j < minLen) { // minLen = i - j; // minJ = j; // } // count[s.charAt(j++) - 'A']++; // found--; // } // return minLen < Integer.MAX_VALUE ? s.substring(minJ, minJ + minLen) : ""; // } // }
-
// OJ: https://leetcode.com/problems/minimum-window-substring/ // Time: O(N) // Space: O(C) where C is the range of characters class Solution { public: string minWindow(string s, string t) { unordered_map<char, int> target, cnt; int len = INT_MAX, i = 0, N = s.size(), matched = 0, begin = 0; for (char c : t) target[c]++; for (int j = 0; j < N; ++j) { if (++cnt[s[j]] <= target[s[j]]) ++matched; while (matched == t.size()) { if (j - i + 1 < len) { len = j - i + 1; begin = i; } if (--cnt[s[i]] < target[s[i]]) --matched; ++i; } } return len == INT_MAX ? "" : s.substr(begin, len); } };
-
from collections import Counter class Solution: def minWindow(self, s: str, t: str) -> str: ans = '' m, n = len(s), len(t) if m < n: return ans need = Counter(t) window = Counter() i, cnt, mi = 0, 0, inf for j, c in enumerate(s): window[c] += 1 if need[c] >= window[c]: # >= , because 1 line above already +=1 cnt += 1 while cnt == n: if j - i + 1 < mi: # in while mi = j - i + 1 ans = s[i : j + 1] c = s[i] if need[c] >= window[c]: # char in window but not in need, need[c]=0, window[c]=1..2.. cnt -= 1 window[c] -= 1 i += 1 return ans ############ class Solution(object): def minWindow(self, s, t): """ :type s: str :type t: str :rtype: str """ score = 0 wanted = collections.Counter(t) start, end = len(s), 3 * len(s) # artitrary 3, just make sure end-start is larger than input s length, for later min-check d = {} deq = collections.deque([]) # using queue to store indexes, good for large ammount of api call for i, c in enumerate(s): if c in wanted: deq.append(i) d[c] = d.get(c, 0) + 1 if d[c] <= wanted[c]: score += 1 while deq and d[s[deq[0]]] > wanted[s[deq[0]]]: d[s[deq.popleft()]] -= 1 if score == len(t) and deq[-1] - deq[0] < end - start: start, end = deq[0], deq[-1] return s[start:end + 1]
-
func minWindow(s string, t string) string { ans := "" m, n := len(s), len(t) if m < n { return ans } need := make([]int, 128) for _, c := range t { need[c] += 1 } window := make([]int, 128) i, cnt, mi := 0, 0, m+1 for j, c := range s { window[c]++ if need[c] >= window[c] { cnt++ } for cnt == n { if j-i+1 < mi { mi = j - i + 1 ans = s[i : j+1] } c = rune(s[i]) if need[c] >= window[c] { cnt-- } window[c]-- i++ } } return ans }
-
function minWindow(s: string, t: string): string { let n1 = s.length, n2 = t.length; if (n1 < n2) return ''; let need = new Array(128).fill(0); let window = new Array(128).fill(0); for (let i = 0; i < n2; ++i) { ++need[t.charCodeAt(i)]; } let left = 0, right = 0; let res = ''; let count = 0; let min = n1 + 1; while (right < n1) { let cur = s.charCodeAt(right); ++window[cur]; if (need[cur] > 0 && need[cur] >= window[cur]) { ++count; } while (count == n2) { cur = s.charCodeAt(left); if (need[cur] > 0 && need[cur] >= window[cur]) { --count; } if (right - left + 1 < min) { min = right - left + 1; res = s.slice(left, right + 1); } --window[cur]; ++left; } ++right; } return res; }
-
using System.Linq; public class Solution { public string MinWindow(string s, string t) { var dict = t.Distinct().ToDictionary(ch => ch, ch => 0); var goalDict = t.GroupBy(ch => ch).ToDictionary(g => g.Key, g => g.Count()); var goal = goalDict.Count; var minI = int.MaxValue; var minJ = 0; var i = 0; var j = 0; var current = 0; while (true) { while (current < goal && i < s.Length) { if (dict.ContainsKey(s[i])) { if (++dict[s[i]] == goalDict[s[i]]) { ++current; } } ++i; } while (current == goal && j < s.Length) { if (dict.ContainsKey(s[j])) { if (dict[s[j]] == goalDict[s[j]]) { break; } else { --dict[s[j]]; } } ++j; } if (current == goal) { if (i - j < minI - minJ) { minI = i; minJ = j; } --dict[s[j]]; --current; ++j; } else { break; } } if (minI == int.MaxValue) { return string.Empty; } else { return s.Substring(minJ, minI - minJ); } } }