76. Minimum Window Substring [Hard]

76. Minimum Window Substring

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.

Constraints:

• m == s.length
• n == t.length
• 1 <= m, n <= 10^5
• s and t consist of uppercase and lowercase English letters.

Example

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

思路

• 并不是需要连续字符串，只是要找出符合预期字符串出现字符个数的子串
• 拆解预期字符串，得出每个字符有多少个，每有一个字符串，就可以认为是一个需要满足的条件
• 看当前子串是否符合条件个数，不符合就继续加字符进来，如果已经符合条件了，就开始从左开始减字符个数，找到最小的子串

题解

    public String minWindow(String s, String t) {
        HashMap<Character, Integer> expectMap = new HashMap<>();
        HashMap<Character, Integer> curMap = new HashMap<>();
        int left, expectCount, curCount;
        String result, temp;
        result = temp = "";
        left = curCount = 0;

        // 先拿到期望字符串的各个字符个数
        for (char c : t.toCharArray())
            expectMap.put(c, expectMap.getOrDefault(c, 0) + 1);
        // 期望字符数
        expectCount = expectMap.size();

        for (int right = 0; right < s.length(); right++) {
            char curChar = s.charAt(right);
            temp += curChar;

            if (expectMap.containsKey(curChar)) {
                curMap.put(curChar, curMap.getOrDefault(curChar, 0) + 1);
                if (curMap.get(curChar).equals(expectMap.get(curChar)))
                    curCount++;
            }

            while (curCount == expectCount) {
                if (result.equals(""))
                    result = temp;
                else
                    result = result.length() > temp.length() ? temp : result;

                char headChar = s.charAt(left);
                if (expectMap.containsKey(headChar)) {
                    curMap.put(headChar, curMap.get(headChar) - 1);
                    if (expectMap.get(headChar) > curMap.get(headChar))
                        curCount--;
                }

                temp = temp.substring(1);
                left++;
            }
        }
        return result;
    }