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 }