76. Minimum Window Substring.md

76. Minimum Window Substring

Problem

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 = "ADOBECODEBANC" T = "ABC" Minimum window is "BANC". tag:

Solution

java

	public String minWindow(String s, String t) {
		Map<Character, Status> map = new HashMap<Character, Status>();
		for (char c : t.toCharArray()) {
			if (map.containsKey(c))
				map.put(c, new Status(map.get(c).cur, map.get(c).target + 1));
			else
				map.put(c, new Status(0, 1));
		}

		int l = 0, r = 0, count = t.length(), minLen = Integer.MAX_VALUE, minLeft = 0;
		for (; r < s.length(); r++) {
			if (map.containsKey(s.charAt(r))) {
				if (map.get(s.charAt(r)).cur < map.get(s.charAt(r)).target)
					count--;
				map.put(s.charAt(r), new Status(map.get(s.charAt(r)).cur + 1, map.get(s.charAt(r)).target));

				for (; count == 0; l++) {
					if (r - l + 1 < minLen) {
						minLen = r - l + 1;
						minLeft = l;
					}
					if (map.containsKey(s.charAt(l))) {
						map.put(s.charAt(l), new Status(map.get(s.charAt(l)).cur - 1, map.get(s.charAt(l)).target));
						if (map.get(s.charAt(l)).cur < map.get(s.charAt(l)).target)
							count++;
					}
				}
			}

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

class Status {
	int cur = 0;
	int target = 0;

	public Status(int c, int t) {
		cur = c;
		target = t;
	}

	public Status() {
	}
}

go