[LeetCode] 76. Minimum Window Substring

Posted on | In

Problem

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

Example:

1
2
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

  • If there is no such window in S that covers all characters in T, return the empty string "".
  • If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

Explanation

  1. Before we start, we need to get the frequency of the string T by using hashmap or an array. Then, we create a matchCount that is used to count the number of matching characters in string T that are matched with the substring, and its maximum length will be the length of T. We will also create a left and right that points at the substring’s beginning and the end. We also need a sArr to hold the substring’s mathing character frequency.

  2. First, we iterating the string S and find the first matching character and use the left and right pointers point at the first matching character, we also need to store its frequency to sArr and update the matchCount if necessary. Then, we find the next matching character, store its frequency and update the matchCount if necessary and we use the right pointer to point at it until we have the same number of matchCount.

  3. For example, S = XXXAXXBAACXXX, T = AABC. Now, left is pointing at the first A, right is pointing at the C, matchCount=4=T.length(), tArr={A=2, B=1, C=1}, sArr = {A=3, B=1, C=1}, and the res is AXXBAAC. Now, we move the left pointer to point at the next match character which is B, the substring is BAAC. We removed one A from sArr, it still has two A, in other word, sArr = {A=2, B=1, C=1} and matchCount not change, and we update the res because now the substring has shorter length than before. Now again, we move the left pointer to point at the next match character which is A, the substring is AAC, and matchCount changed to 3, so we move the right pointer points to the next matching character and repeat this process until it hits the end.

Solution

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
40
41
42
43
44
45
46
47
48
49
class Solution {
    int findNextValidIdx(int start, String s, int[] tArr) {
        while (start < s.length()) {
            char c = s.charAt(start);
            if (tArr[c] != 0) return start;
            start += 1;
        }
        return start;
    }
    
    public String minWindow(String s, String t) {
        if (s == null || s.length() == 0 || t == null || t.length() == 0) return "";
        
        String res = "";
        int matchCount = 0;
        int[] tArr = new int[256];
        for (char c : t.toCharArray()) {
            tArr[c] += 1;
        }
        
        int[] sArr = new int[256];
        int left = findNextValidIdx(0, s, tArr);
        if (left == s.length()) return "";
        int right = left;
        while (right < s.length()) {
            int rightChar = s.charAt(right);
            if (sArr[rightChar] < tArr[rightChar]) {
                matchCount += 1;
            }
            sArr[rightChar] += 1;
            
            while (left < s.length() && matchCount == t.length()) {
                if (res.isEmpty() || res.length() > right-left+1) {
                    res = s.substring(left, right+1);
                }
                int leftChar = s.charAt(left);
                if (sArr[leftChar] <= tArr[leftChar]) {
                    matchCount -= 1;
                }
                sArr[leftChar] -= 1;
                left = findNextValidIdx(left+1, s, tArr);
            }
            
            right = findNextValidIdx(right+1, s, tArr);
        }
        
        return res;
    }
}