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

For example,

S = "STUVSTV"

T = "STV"

Minimum window is "STUV".

This is one of the most common and favorite interview questions for engineers.

Lets start with creating the counter, which will keep count of characters. It could a HashMap.

counter:
[ S -1, T-1, V-1 ]
Start with two pointers, maintaining the index of string S:
start, end = 0
have a length variable set to length of T string.
length = 3
  • Start incrementing the end index.
  • Check at the end index of S, if the character is in counter map and count > 0, decrement the length.
  • keep doing it until length is 0. When length is zero, it means we found a window which contains all the characters from string.T
  • The length of string is the difference between end - start. Track whether the difference is minimum.
  • Now start incrementing the start pointer, unless one of the input character is found. Track whether the difference is minimum between end - start.
  • Continue until end of string S is reaced.

Lets look at the above example

counter:
[ S -1, T-1, V-1 ]
start,end = 0
length = 3
S = "STUVSTV"
T = "STV"

at start = 0, end = 0, S[end] = 'S'
update:
[ S -0, T-1, V-1 ]
incr end: start = 0, end = 1
length = 2

at start = 0, end = 1, S[end] = 'T'
update:
[ S -0, T-0, V-1 ]
incr end: start = 0, end = 2
length = 1

at start = 0, end = 2, S[end] = 'U'
update:
[ S -0, T-0, V-1 ]
incr end: start = 0, end = 3
length = 1

at start = 0, end = 3, S[end] = 'V'
update:
[ S -0, T-0, V-0 ]
incr end: start = 0, end = 3
length = 0
window = end-start+1 = 4 "STUV"

at start = 1, end = 3, S[start] = 'S'
update:
[ S-1, T-0, V-0 ]
incr start: start = 1, end = 3
length = 1

at start = 1, end = 4, S[end] = 'S'
update:
[ S-0, T-0, V-0 ]
incr end: start = 1, end = 3
length = 0
window = end-start+1 = 4 "TUVS"

at start = 1, end = 4, S[start] = 'S'
update:
[ S-0, T-1, V-0 ]
incr start: start = 2, end = 4
length = 1

at start = 2, end = 5, S[end] = 'T'
update:
[ S-0, T-0, V-0 ]
incr end: start = 2, end = 6
length = 0
window = end-start+1 = 4 "UVST"

at start = 2, end = 5, S[end] = 'U'
update:
[ S-0, T-0, V-0 ]
incr start: start = 3, end = 6
length = 0

at start = 3, end = 5, S[start] = 'V'
update:
[ S-0, T-0, V-1 ]
incr start: start = 4, end = 6
length = 1

at start = 4, end = 5, S[end] = 'V'
update:
[ S-0, T-0, V-0 ]
incr end: start = 4, end = 6
length = 0
window = end-start+1 = 3 "STV"
public class MinWindowSubString {

	public static void main(String[] args) {
		System.out.println(new MinWindowSubString()
							.minWindow("bcadeac", "aea"));
	}

	String minWindow(String s, String t) {
		int maxWind = Integer.MAX_VALUE;
		int tArr[] = new int[128];
		for (char ch : t.toCharArray()) {
			tArr[ch] = tArr[ch] + 1;
		}
		int end = 0;
		int begin = 0;
		int counter = t.length();
		int head = begin;
		while (end < s.length()) {
			if (tArr[s.charAt(end)] > 0) {
				counter--;
				tArr[s.charAt(end)]--;
			}
			end--;
			while (counter == 0) {
				if (end - begin < maxWind) {
					maxWind = end - begin;
					head = begin;
				}
				if (tArr[s.charAt(begin)] == 0) {
					counter++;
					tArr[s.charAt(begin)]++;
				}
				begin++;
			}
		}
		return maxWind == Integer.MAX_VALUE ? "" :
						 s.substring(head, head + maxWind);
	}
}