</>Ali · LeetCode
#0076·HardSliding Window

Minimum Window Substring

LeetCode #76 · Hard · Sliding Window · C++ solution with worked-out approach and complexity analysis.

View on LeetCodeSource on GitHub

Approach

Sliding Window

Strategy

  1. 1Use a frequency map (vector of size 128) to store counts of characters
  2. 2Use two pointers, 'begin' and 'end', to define a window [begin, end).
  3. 3Expand the window by moving 'end' forward:
  4. 4When 'counter' becomes 0 (all characters from t are found):
  5. 5Repeat until 'end' reaches the end of s.
Time
O(m + n)
Space
O(1)
(since map size is fixed at 128)
Problem description(from LeetCode)

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"
Note:
The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t. Input: s = "a", t = "a" Output: "a" 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^5
  • •s and t consist of uppercase and lowercase English letters.

C++ Solution

solution.cpp
class Solution {
public:
string minWindow(string s, string t) {
    vector<int> map(128, 0);
    for (auto 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--;
      }
      map[s[end]]--;
      end++;

      while (counter == 0) { // valid
        if (end - begin < d) {
          d = end - begin;
          head = begin;
        }

        map[s[begin]]++;
        if (map[s[begin]] > 0) {
          counter++; // make it invalid
        }
        begin++;
      }
    }
    return d == INT_MAX ? "" : s.substr(head, d);
  }
};

More Sliding Window problems