Minimum Window Substring

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

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

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

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

class Solution {
    public String minWindow(String s, String t) {
        // Using array because this was faster than using HashMap
        int[] map = new int[128];
        for (char c : t.toCharArray())
            map[c]++;
        int start = 0, end = 0, minStart = 0, minLen = Integer.MAX_VALUE, counter = t.length();
        while (end < s.length()) {
            char c1 = s.charAt(end);
            if (map[c1] > 0)
                counter--;
            map[c1]--;
            while (counter == 0) {
                if (minLen > end - start + 1) {
                    minLen = end - start + 1;
                    minStart = start;
                }
                char c2 = s.charAt(start);
                map[c2]++;
                if (map[c2] > 0)
                    counter++;
                start++;
            }
            end++;
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
    }
}