Minimum Window Substring

LeetCode Q 76 - 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.

Solution

Solution : Sliding window + HashTable

arr[]: denotes how many letters are still in the string T. e.g. if t = “abc”, then in the array values of ‘a’, ‘b’ and ‘c’ are both 1.
So, during our traversal of the string S, when we encounter ‘a’, we update the table, changing the value of ‘a’ to be 0. Next time we encounter ‘a’, we change the value of ‘a’ to be -1 …

count: denotes how many chars are still required to get a window in S that containing all letters in T. if (count == 0), we update minLen.

Code:

public String minWindow(String s, String t) {
	if (t.length() == 0 || t.length() > s.length()) return "";
	
	int[] arr = new int[256];
	for (char ch: t.toCharArray()) arr[ch]++;

	int count = t.length(), l = 0, r = 0, minLen = Integer.MAX_VALUE, head = 0;
	while (r < s.length()) {
		if (arr[s.charAt(r)] > 0) count--;
		arr[s.charAt(r++)]--;
		while (count == 0) {   // if is not correct
			if (r - l < minLen) { minLen = r - l; head = l; }
			if (arr[s.charAt(l)] >= 0) count++;
			arr[s.charAt(l++)]++;
		}
	}

	return minLen == Integer.MAX_VALUE ? "" : s.substring(head, head + minLen);
}