Minimum Window Substring – Java

The brute force method would be calculate all the substrings, which would be inefficient.

Runtime Complexity O(m + n)

Space Complexity O(m+n)

class Solution {
    public String minWindow(String s, String t) {
        int tLen = t.length();
        int sLen = s.length();
        if (tLen > sLen)
            return "";
        int[] pattern = new int[256];
        int[] given = new int[256];
        for (int i = 0; i < tLen; i++)
            pattern[t.charAt(i)]++;
        int mstart = 0, size = 0, start = 0, min = sLen + 1;
        for (int j = 0; j < s.length(); j++) {
            char curr = s.charAt(j);
            if (given[curr] < pattern[curr])
                size++;
            given[curr]++;
            if (size == tLen) {
                while (given[s.charAt(start)] > pattern[s.charAt(start)]) {
                    given[s.charAt(start)]--;
                    start++;
                }
                int len = j - start + 1;
                if (len < min) {
                    min = len;
                    mstart = start;
                }
            }
        }
        if (size < tLen)
            return "";
        return s.substring(mstart, mstart + min);
    }
}