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 and t 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.

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

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

  3. When moving the left pointer in the while loop, the condition found[s.charAt(left)]> 1 should be replaced with found[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.

  4. 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);
            }
        }
    }
    

All Problems

All Solutions