Minimum Window Substring

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.

Examples

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints:

• m == s.length
• n == t.length
• 1 <= m, n <= 10^5
• s and t consist of uppercase and lowercase English letters.

Follow up:

Could you find an algorithm that runs in O(m + n) time?

解析

給定兩個字串 s, t

要求寫一個演算法找出 s 的子字串中包含 t 字串所有字元的最短子字串

s 的子字串 p 代表 p 中所有字元都在 s 出現過且每個字元必須跟 s 的相鄰狀態相同

所以題目要找子字串 p 必須要

1. 包含所有 t 的字元

2. 必須是字元相連性跟原本 s 相同

3. 必須是最短的

第一個條件可以透過 hashmap 的方式把 t 的所有字元出現次數紀錄下來比對

第二個相鄰狀態可以透過 slide-window 方式來保證

第三個條件 可以知道最理想的狀態是 剛好子字串長度跟 t 字串長度一樣

所以從子字串長度 == t 字串長度 且累計配對字元數相等時

就可以不斷更新 最小子字串長度直到把所有 s 的可能右界都走完 就可以找到最小的那個長度了

具體作法是大致分成三大步驟

1 在 slide-window 還沒有包含足夠多的字元時， 把右界往右

2 當符合條件具有足夠多的字元時，更新當 slide-window 比上一次符合條件小時，更新 slide-window 的 size 並且紀錄當下左右界

3 開始把左界左移，並且檢查當下 slide-window 是否有更小

具體作法如下圖

透過 sliding window 策略，只要把 sliding window 左界從字串最左邊找到字串最右邊

則可以把所有可能都找完，這樣就能找出最小長度的子字串

時間複雜度為 O(n)

而窮舉法會需要從每個起始點開始把可能的結束點都找完

對每個起始點 start = 0..n-1 , 結束點有 end = start..n-1 可能

所以窮舉法的時間複雜度是 O(n^2)

sliding window 策略有效的把可能值給限縮範圍加快了搜尋速度

空間複雜度是 O(1)

因為只需要紀錄當下 sliding window 左右界還有最小 sliding window 左右界

程式碼

package sol

func minWindow(s string, t string) string {
	sLen, tLen := len(s), len(t)
	sFreq, tFreq := make([]int, 256), make([]int, 256)
	result := ""
	count := 0
	left, right, subLeft, subRight := 0, -1, -1, -1
	minW := sLen + 1
	if sLen < tLen || sLen == 0 || tLen == 0 {
		return result
	}
	for pos := 0; pos < tLen; pos++ {
		tFreq[t[pos]]++
	}
	for left < sLen {
		// check if right not reach end and count
		if right+1 < sLen && count < tLen {
			if sFreq[s[right+1]] < tFreq[s[right+1]] {
				count++
			}
			sFreq[s[right+1]]++
			right++
		} else {
			if right-left+1 < minW && count == tLen { // smaller window exist
				minW = right - left + 1
				subLeft = left
				subRight = right
			}
			// shift left point to right
			if sFreq[s[left]] == tFreq[s[left]] {
				count--
			}
			sFreq[s[left]]--
			left++
		}
	}
	if subLeft != -1 {
		result = s[subLeft : subRight+1]
	}
	return result
}

困難點

1. 需要理解透過 HashTable 確認字元出現個數的方法
2. 需要知道 slide-window 找尋可能子字串的方式

Solve Point

• [x] 初始化 s_freq , t_freq 兩個 HashTable 用來各自紀錄 s, t 的字元次數出現狀況, count= 0 用來紀錄 s match 到 t 的字元個數， left = 0, right = -1, sub_left = -1, sub_right = -1, minW = len(s)+1
• [x] 先把 t 的字元次數紀錄在 t_freq
• [x] 當 left < len(s) 做以下運算
• [x] 當 right + 1 < len(s) && count < len(t) 時 , 代表 還沒蒐集夠子字串字元 做以下運算
• [x] 更新 s_freq[s[right+1]] += 1
• [x] 當 s_freq[s[right+1]] ≤ t_freq[s[right+1]] 時 代表 該字元需要被納入 , 更新 count = count+1
• [x] 更新 right = right + 1
• [x] 當 right + 1 == len(s) || count == len(t) 時，做以下運算
• [x] 當 right - left + 1 < minW 且 count == len(t) 時 代表已經蒐集足夠字元當子字串， 更新 minW = right - left + 1 , 更新 sub_left = left, sub_right = right
• [x] 當 s_freq[s[left]] == t_freq[s[left]] 時 , 代表要左移的字元有被算入 count 之中 , 更新 count = count - 1 來做還原
• [x] 更新 s_freq[s[left]] -= 1, left = left + 1
• [x] 當跑到最後 sub_left ≠ -1 代表有找到子字串所以回傳 s[sub_left: sub_right+1], 否則回傳 “”