Skip to main content

Minimum Window Substring(LeetCode)

Problem Statement​

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.

Examples​

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.

Solution​

Approach 1: C++​

Algorithm​

  1. Initialization:
  • Create a map to count characters in t.
  • Initialize counter to the length of t, begin and end pointers to 0, d (length of the minimum window) to INT_MAX, and head to 0.
  1. Expand the Window:
  • Move the end pointer to expand the window.
  • Decrease the count in map for the current character in s.
  • If the count in map is greater than 0, decrement counter.
  1. Shrink the Window:
  • When counter is 0, try to shrink the window by moving the begin pointer.
  • If the new window size is smaller, update head and d.
  • Increase the count in map for the character at begin.
  • If the count in map becomes positive, increment counter.
  1. Return Result:
  • If d is still INT_MAX, return an empty string.
  • Otherwise, return the substring starting from head with length d.

Implementation​

class Solution {
public:
string minWindow(string s, string t) {
vector<int> map(128, 0);
for (char c : t) {
map[c]++;
}

int counter = t.size(), begin = 0, end = 0, d = INT_MAX, head = 0;
while (end < s.size()) {
if (map[s[end++]]-- > 0) {
counter--;
}
while (counter == 0) {
if (end - begin < d) {
head = begin;
d = end - head;
}
if (map[s[begin++]]++ == 0) {
counter++;
}
}
}
return d == INT_MAX ? "" : s.substr(head, d);
}
};

Complexity Analysis​

  • Time complexity: O(M+N)O(M+N)
  • Space complexity: O(1)O(1)

Approach 2: Python​

Algorithm​

  1. Initialization:
  • Create a needstr dictionary to count characters in t.
  • Initialize needcnt to the length of t, res to store the result window, and start to 0.
  1. Expand the Window:
  • Move the end pointer to expand the window.
  • Decrease the count in needstr for the current character in s.
  • If the count in needstr is greater than 0, decrement needcnt.
  1. Shrink the Window:
  • When needcnt is 0, try to shrink the window by moving the start pointer.
  • Adjust the count in needstr for the character at start.
  • If the count in needstr becomes positive, increment needcnt.
  1. Return Result:
  • If the result window is valid, return the substring.
  • Otherwise, return an empty string.

Implementation​

class Solution:
def minWindow(self, s: str, t: str) -> str:
if len(s) < len(t):
return ""
needstr = collections.defaultdict(int)
for ch in t:
needstr[ch] += 1
needcnt = len(t)
res = (0, float('inf'))
start = 0
for end, ch in enumerate(s):
if needstr[ch] > 0:
needcnt -= 1
needstr[ch] -= 1
if needcnt == 0:
while True:
tmp = s[start]
if needstr[tmp] == 0:
break
needstr[tmp] += 1
start += 1
if end - start < res[1] - res[0]:
res = (start, end)
needstr[s[start]] += 1
needcnt += 1
start += 1
return '' if res[1] > len(s) else s[res[0]:res[1]+1]

Complexity Analysis​

  • Time complexity: O(M+N)O(M+N)
  • Space complexity: O(N)O(N)

Conclusion​

The C++ and Python approaches for finding the minimum window substring are quite similar in their methodology. Both utilize the two-pointer technique, also known as the sliding window approach, to efficiently traverse the string s and dynamically adjust the window to find the smallest valid substring containing all characters of the string t. They maintain a character count map to keep track of the required characters from t and adjust the counts as the window expands and contracts. Additionally, both solutions use a counter variable to monitor the number of characters still needed to form a valid window.