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.
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 必須要
包含所有 t 的字元
必須是字元相連性跟原本 s 相同
必須是最短的
第一個條件可以透過 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
}