LeetCode link

Intuition

  • Using two pointer to border the sliding window.
  • Using a map to save the count of each character appearance and a map to save the count of character in the window.

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
class Solution {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }
        int[] expectCount = new int[256];
        int[] nowCount = new int[256];
        for (int i = 0; i < t.length(); i++) {
            expectCount[t.charAt(i)]++;
        }
        int minLength = Integer.MAX_VALUE;
        String result = "";
        int count = 0;
        for (int begin = 0, end = 0; end < s.length(); end++) {
            char c = s.charAt(end);
            if (expectCount[c] <= 0) {
                continue;
            }
            nowCount[c]++;
            count++;
            if (count >= t.length()) {
                while (expectCount[s.charAt(begin)] <= 0 || nowCount[s.charAt(begin)] > expectCount[s.charAt(begin)]) {
                    if (nowCount[s.charAt(begin)] > expectCount[s.charAt(begin)]) {
                        count--;
                        nowCount[s.charAt(begin)]--;
                    }
                    begin++;
                }
                if (end - begin + 1 < minLength) {
                    result = s.substring(begin, end + 1);
                    minLength = end - begin + 1;
                }
            }
        }
        return result;
    }
}

problem

WA.

reason

When adding the count, it didn’t take consider of the duplicate chars, so maybe the count is greater or equal to the length of t, but maybe there’s some wrong case(such as window is [b,b] but t is [a,b]).

modification

Need to avoid the duplicate case.

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
class Solution {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }
        int[] expectCount = new int[256];
        int[] nowCount = new int[256];
        for (int i = 0; i < t.length(); i++) {
            expectCount[t.charAt(i)]++;
        }
        int minLength = Integer.MAX_VALUE;
        String result = "";
        int count = 0;
        for (int begin = 0, end = 0; end < s.length(); end++) {
            char c = s.charAt(end);
            if (expectCount[c] <= 0) {
                continue;
            }
            nowCount[c]++;
            if (nowCount[c] <= expectCount[c]) {
                count++;
            }
            if (count >= t.length()) {
                while (expectCount[s.charAt(begin)] <= 0 || nowCount[s.charAt(begin)] > expectCount[s.charAt(begin)]) {
                    if (nowCount[s.charAt(begin)] > expectCount[s.charAt(begin)]) {
                        nowCount[s.charAt(begin)]--;
                    }
                    begin++;
                }
                if (end - begin + 1 < minLength) {
                    result = s.substring(begin, end + 1);
                    minLength = end - begin + 1;
                }
            }
        }
        return result;
    }
}