Minimum Window Substring

1package pkg5leetcode.blind75;2 3/*4 * Minimum Window Substring | LC 765 * APPROACH: Expand right until valid; shrink left while valid.6 * COMPLEXITY: Time O(n), Space O(1) alphabet7 */8public class blind75_LC76MinimumWindowSubstring {9    static String minWindow(String s, String t) {10        if (t.length() > s.length()) return "";11        int[] need = new int[128], have = new int[128];12        for (char c : t.toCharArray()) need[c]++;13        int required = t.length(), formed = 0;14        int left = 0, bestLen = Integer.MAX_VALUE, bestStart = 0;15        for (int right = 0; right < s.length(); right++) {16            char rc = s.charAt(right);17            if (need[rc] > 0 && ++have[rc] <= need[rc]) formed++;18            while (formed == required) {19                if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestStart = left; }20                char lc = s.charAt(left++);21                if (need[lc] > 0 && --have[lc] < need[lc]) formed--;22            }23        }24        return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);25    }26 27    public static void main(String[] args) {28        check(minWindow("ADOBECODEBANC", "ABC").equals("BANC"), "case1");29        check(minWindow("a", "a").equals("a"), "case2");30        System.out.println("all tests passed");31    }32 33    static void check(boolean cond, String name) {34        if (!cond) throw new AssertionError("FAILED: " + name);35        System.out.println("  PASS " + name);36    }37}