Leetcode - Find K-Length Substrings With No Repeated Characters
Leetcode - Sliding Window Maximum

Leetcode - Minimum Window Substring

violet posted @ May 15, 2020 06:34:48 AM in 算法 with tags Algorithm Golang SlidingWindow , 264 阅读

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
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter