Question

Formatted question description: https://leetcode.ca/all/76.html

76. Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the empty string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Algorithm

Swipe directly from one direction on the left.

1 . The key point is how to move the left pointer when scanning a string. The i in for is equivalent to the right pointer. Move left to the char in the first target, while ensuring that the found number of this char is greater than the number in the target

2 . The question of when to compare with min, I started with the same length as count and target, so I directly compared with min This is wrong. For example, AAAABC, count is equal only when it reaches C, but you must shrink first, and then compare with min

3 . When the while loop moves to the left, found[s.charAt(left)]> 1, I wrote it wrong, not 1, but the number required in the target found[s.charAt(left)]> target[s.charAt(left)

  • Must be greater than, because entering while requires –, - and then it is exactly equal to what target needs

4 . The processing of result, at the beginning I wrote two ints to record the position of the smallest window. In fact, you can directly write a string to be initially empty, and assign min every time

  • This way, you don’t need to judge whether int is negative or not, to see if there are results.

Code

Java

  • 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;
            }
        }
    
    }
    
  • // 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);
        }
    };
    
  • 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)
        d = {}
        deq = collections.deque([])
        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]
    
    

All Problems

All Solutions