Leetcode - Minimum Window Substring
https://leetcode.com/problems/minimum-window-substring/
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 {
hash := map[byte]int{}
count := 0
for i := 0; i < len(t); i++ {
if hash[t[i]] == 0 {
count++
}
hash[t[i]]++
}
result := ""
c := 0
for i, j := 0, 0; i < len(s); i++ {
if hash[s[i]] == 1 {
c++
}
hash[s[i]]--
for hash[s[j]] < 0 {
hash[s[j]]++
j++
if j > i {
break
}
}
if c == count {
if result == "" || len(result) > i - j + 1 {
result = s[j:i+1]
}
}
}
return result
}
评论 (0)
