Gyh's Braindump

76. Minimum Window Substring

tags
sliding window, subarray
source
leetcode

Edge Cases

"aa"
"aa"
"aaflslflsldkalskaaa"
"aaa"
"abc"
"a"

Solution

class Solution {
    public String minWindow(String s, String t) {
        int[] count = new int[128];

        char[] sArray = s.toCharArray();
        char[] tArray = t.toCharArray();

        int found = 0, required = 0;
        for (char c: tArray) {
            count[c]++;
            required++;
        }

        int minL = -1, minR = -1;
        for (int l = 0, r = 0; r < sArray.length; r++) {
            count[sArray[r]]--;

            if (count[sArray[r]] >= 0) found++;

            if (found == required) {
                while (count[sArray[l]] != 0) count[sArray[l++]]++;
                if (minR == -1 || (r - l) < (minR - minL)) {
                    minR = r;
                    minL = l;
                }
                count[sArray[l++]]++;
                found--;
            }
        }

        return minR == -1 ? "" : s.substring(minL, minR + 1);
    }
}

Complexity

  • time: O(N)
  • space: O(N + M)