Description
tags: Hash Table, Two Pointers, String difficulty: Hard
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).
Example:
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
Note:
If there is no such window in S that covers all characters in T, return the empty string "". If there is such window, you are guaranteed that there will always be only one unique minimum window in S.
func minWindow(s string, t string) string {
if len(s) == 0 || len(t) == 0 {
return ""
}
mapT := make([]int, 256)
for i:=0;i<len(t);i++{
mapT[int(t[i])]+=1
}
posPair := []int{-1,-1}
counter := len(t)
minWin := len(s)
start :=0
for index,val := range s{
mapT[int(val)] -=1
if mapT[int(val)] >= 0{
counter--
}
for ;counter==0;start++ {
if minWin > index - start {
posPair[0] = start
posPair[1] = index
minWin = index - start
}
mapT[int(s[start])]+=1
if mapT[int(s[start])] > 0 {
counter++
}
}
}
if posPair[0] == -1 {
return ""
}
return s[posPair[0]:posPair[1]+1]
}
这是一个滑动窗口的算法题,基本的滑动窗口算法窗口大小是固定的,本题是滑动窗口的一个变体应用。
应用方向:求连续大小为K的子数组的最大最小的值,和,积,xor 等
例子:Given an array of integers of size ‘n’. Our aim is to calculate the maximum sum of ‘k’ consecutive elements in the array.
基本滑动窗口大小是固定的,而一般滑动窗口的大小是需要我们自己计算的,本题就是一例,根据网友的总结10-line template that can solve most 'substring' problems, 很多的子字符串类题都可以使用这种方法。