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 <= 10⁵
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.

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

76 - Minimum Window Substring

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions