MinimumWindowSubstring [source code]

public class MinimumWindowSubstring {
static
/******************************************************************************/
public class Solution {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) return "";
        int[] hash = new int[256];
        char[] chs = s.toCharArray(), cht = t.toCharArray();
        for (char c : cht) {
            hash[c]++;
        }
        int[] res = new int[2];
        int lo = 0, hi = 0, count = cht.length, minLen = Integer.MAX_VALUE;
        while (hi < chs.length) {
            char c = chs[hi];
            if (hash[c] >= 1) {
                count--;
            }
            hash[c]--;
            hi++;

            while (count == 0) {
                if (hi - lo < minLen) {
                    minLen = hi - lo;
                    res[0] = lo;
                    res[1] = hi;
                }
                char prev = chs[lo++];
                if (hash[prev]++ >= 0) count++;
            }
        }
        return s.substring(res[0], res[1]);
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        MinimumWindowSubstring.Solution tester = new MinimumWindowSubstring.Solution();
        String[] inputs = {
            "ADOBECODEBANC", "ABC",
            "ADOBECODEBANCADOBECODEBANC", "ABC",
            "ADOBECODEBANCADOBECODEBANC", "ABBC",
            "ADOBECODEBANC", "ZZZ",
            "a", "a",
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            String s = inputs[2 * i];
            String t = inputs[1 + 2 * i];
            System.out.println(s + " VS " + t + " -> " + tester.minWindow(s, t));
        }
    }
}

正好别的题目看到sliding window的算法, 干脆把这一题做掉, 因为这一题的 discussion 里面有一个对 sliding window 问题超级好的总结; 放到 bear 里面去了, 放这里太乱了.

刚开始写代码不要太追求++inline这样的东西, 一来是容易错, readability 不好, 二来, 真正在面试的时候, 你敢这么写吗? 面试官要么认为你是背过代码, 要么就认为你是在卖弄聪明; 反正这个东西就是得不偿失, 而且还属于 Premature Optmization;

这个问题属于是sliding window算法的一个巩固题了, 我没有刻意去记那几个模板, 不过这个题目的写法跟第一个模板还是很多相似之处的. 这个问题总体思路跟前面 anagram 那一题其实是类似的, 唯一的难点在于, 你怎么处理 slide的情形. 在 anagram 那一题, 因为 window 的 size 是固定的, 所以只要你知道长度, 就可以确定 slide.
但是这一题不一样, 这一题没有固定长度, 需要针对具体问题具体分析. 首先要记住, count 就是 success 的意思. 这里的逻辑就是, 一旦 success, 我们就从左边开始踢人, 一直踢到不再 success 为止, 然后重新从右边加人.

这个题目还有一点小的细节需要处理的是, 你怎么处理fail-case和bad-case.
bad-case 就是开头对长度进行一下判断;
幸运的是, 这一题不需要单独处理 fail case, 因为如果找不到的话, 那么最后res 里面的 lo和 hi 存的就都是0, 那么最后的 substring 返回的自动就是一个空 string;

最后的速度是3ms (98%), 意外的好;

另外这里 minLen 的初始化的值值得注意. 我一开始很想当然的就直接初始化到chs.length, 不过这个是不对的, 后面"a", "a"这个 case 就是用来break 这个情形的. 老老实实初始化到 MAX 就行了;

另外上一个问题的时候有一点没有讨论, 就是sliding window算法为什么是O(N), 因为表面上来看, 这里其实是有一个nested loop的. 这个是因为从 aggregate 的角度来看, lo 和 hi 两个指针都是每个人最多只能移动O(N), 而且两个指针都不后退; 所以最后的 iteration 数量顶多就是O(N);

Problem Description

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

For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the empty string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Difficulty:Hard
Total Accepted:103.3K
Total Submissions:413.6K
Contributor: LeetCode
Companies
linkedin snapchat uber facebook
Related Topics
hash table two pointers string
Similar Questions
Substring with Concatenation of All Words Minimum Size Subarray Sum Sliding Window Maximum Permutation in String Smallest Range