[LeetCode] 76. Minimum Window Substring

轉自LeetCode

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

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

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

<Solution>

這題要在 string S中找到最小 substring，可以包含 string T 裡面所有的字元

解題想法如下(參考資料)

• 用個 map 代表在 string T 裡面有出現過的字元

• 準備兩個指針代表 substring 的開始和結束，以及一個 count，其初始值是 string T 的長度

• 開始歷遍 string S，當遇到同樣有在 string T 裡面的字元時，就把 count 減一

• 每個歷遍的字元，都要去 map 裡面對應的位置減一，代表被歷遍過了

• 當 count 等於零的時候，代表目前 start 和 end 所代表的 substring 包含了所有 string T 的字元，這時候開始移動 start 來找到最短的 substring

• 如果目前 start 和 end 代表的 substring，其長度比目前的最小值還短，更新最小值資訊

• 將 start 目前所指到的字元，在 map 裡對應位置的值加一，要是其值加一後是大於零的，代表該字元同時也是在 string T 裡，這時候要把 count 加一

• 只要 count 還是等於零，就一直移動 start。因為 count 等於零，就代表目前的 substring 包含 string T 裡面的所有字元

code 如下
cpp

	class Solution {
	public:
	string minWindow(string s, string t) {
	if(t.length() > s.length()) {
	return "";
	}
	//> map is used to check the char in s also exists in t or not
	vector<int> map(256, 0);
	for(auto c : t) {
	++map[c];
	}
	int start = 0, end = 0, count = t.length();
	int minStart = 0, minLen = INT_MAX;
	while(end < s.length()) {
	//> if char in s exists in t, decrease count
	if(map[s[end]] > 0) {
	--count;
	}
	//> decrease map[s[end]]
	//> if char does not exist in t, m[s[end]] will be negative
	--map[s[end]];
	//> move end
	++end;
	//> when we find a valid window
	//> move start to find smaller window
	while(count == 0) {
	if((end - start) < minLen) {
	minStart = start;
	minLen = end - start;
	}
	//> invalid current start position of window
	++map[s[start]];
	//> when char exists in t, increase counter
	if(map[s[start]] > 0) {
	++count;
	}
	//> move start to find small valid window
	++start;
	}
	}
	return (minLen == INT_MAX) ? "" : s.substr(minStart, minLen);
	}
	};

view raw findMinWindowSubstring.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun minWindow(s: String, t: String): String {
	val map = mutableMapOf<Char,Int>()
	for(c in t) {
	map[c] = map[c]?.let { it + 1 } ?: 1
	}
	var ans = ""
	var cnt = 0
	var left = 0
	var min = Int.MAX_VALUE
	for(right in s.indices) {
	if(map.containsKey(s[right])) {
	map[s[right]] = map[s[right]]!! - 1
	if(map[s[right]]!! >= 0) {
	++cnt
	}
	}
	while(cnt == t.length) {
	if (min > right - left + 1) {
	min = right - left + 1
	ans = s.substring(IntRange(left, right))
	}
	if(map.containsKey(s[left])) {
	map[s[left]] = map[s[left]]!! + 1
	if (map[s[left]]!! > 0) {
	--cnt
	}
	}
	++left
	}
	}
	return ans
	}
	}

view raw minimum_window_substring.kt hosted with ❤ by GitHub