Minimum Window Substring Problem


Description

LeetCode Problem 76.

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.

A substring is a contiguous sequence of characters within the string.

Example 1:

1
2
3
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

1
2
3
Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

1
2
3
4
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.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    string minWindow(string s, string t) {
        int len_s = s.size();
        int len_t = t.size();
        
        unordered_map<char, int> ht;
        for (int i = 0; i < len_t; i ++) {
            ht[t[i]] ++;
        }
        
        int i = 0, j = 0;
        int cnt = ht.size();
        int min_win = INT_MAX;
        string ans;
        for (i = 0; i < len_s; i ++) {
            while ((cnt != 0) && (j < len_s)) {
                if (ht.find(s[j]) != ht.end()) {
                    ht[s[j]] --;
                    if (ht[s[j]] == 0)
                        cnt --;
                }
                j ++;
            }
            if ((cnt == 0) && (min_win > j - i)) {
                min_win = j - i;
                ans = s.substr(i, j - i);
            }
            if (t.find(s[i]) != string::npos) {
                ht[s[i]] ++;
                if (ht[s[i]] > 0)
                    cnt ++;
            }
            

        }
        return ans;
    }
};




Related Posts

Longest Consecutive Sequence Problem

LeetCode 128. Given an unsorted array of integers nums, return...

Set Matrix Zeroes Problem

LeetCode 73. Given an m x n integer matrix matrix,...

Minimum Window Substring Problem

LeetCode 76. Given two strings s and t of lengths...

Search in Rotated Sorted Array Problem

LeetCode 36. Determine if a 9 x 9 Sudoku board...

Integer to Roman Problem

LeetCode 12. Given an integer, convert it to a roman...