Minimum Window Substring 最小窗口子串

问题

[76] Minimum Window Substring  

https://leetcode.com/problems/minimum-window-substring/description/

* algorithms
* Hard (31.68%)
* Total Accepted:    267.2K
* Total Submissions: 841.8K
* Testcase Example:  '"ADOBECODEBANC"\n"ABC"'

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.

解析

据说窗口移动问题是疏通Array各种问题中的关键的关键。

这道Leetcode上难度为hard的题目显然就是传说中的不会做就是100年不会的题目。

看完别人的分析，我们来自己分析一下。

这个题目的核心就是，首先移动右边界，去寻找一个符合条件的字符串，记录下这个字符串的长度，然后移动左边界，直到去掉一个关键的字符，然后再试着移动右边界，去寻找一个比刚刚更短的符合条件的字符串。

详细来说，

首先，我们用一个hash来记录T中各个字符出现的次数。记做hash_t。

那么例子中，我们获得的hash_t就是{a=>1, b=>1, c=>1}。

接下来我们逐个遍历s中的每个字符,假设当前位置为i。每当我们遇到t中出现的字符，就将hash_t[s[i]]对应地减去1。

当hash_t[s[i]]为0的时候，我们知道我们已经找到了符合要求的一个字符，所以我们可以另外用一个cnt，初始值为0，每当hash_t[s[i]]为0，我们就将cnt加上1。
同时，我们将hash_t[s[i]]减去1。

想想一下我们可能遇到hash_t[s[i]] 为负数的情况，但是这个也不要紧，这说明当前字符串s中已经有了多个在t中出现的相同字符。

当cnt等于t的长度，说明我们已经找齐了所有的t中的字符，这个时候可以将当前从左边界到右边界的字符串和目前已经知道的最短符合条件的字符串进行比较。

接下来，移动左边界left。当左边界的字符不在我们hash_t中的时候，我们不断移动左边界。当左边字符在hash_t中，我们将hash_t[s[left]]加上1。并将cnt减去1.
当hash_t[s[left]]变为0以上，说明我们又缺乏了s[left],所以需要移动右边界去继续寻找。。。

Ruby 解法

def min_window(s, t)
  hash_t = {}
  t.split("").each do |c|
    hash_t[c] ||=0
    hash_t[c]+=1
  end
  cnt = 0
  left = 0
  min = 2**31 - 1
  result = ""
  for i in 0..s.length - 1
    right = s[i]
    if hash_t[right]
      hash_t[right] -=1
      cnt +=1 if hash_t[right] >= 0
    end
    while cnt == t.length
      if min > i - left + 1
        min = i - left + 1
        result = s[left...left+min]
      end
      if hash_t[s[left]]
        hash_t[s[left]] +=1
        cnt -=1 if hash_t[s[left]] > 0
      end
      left +=1
    end
  end
  return result
end

反思

刷题的话并不是要发明什么，所以百思不得其解的时候，去看一下答案还是有必要的。