String

Question 1

30. Substring with Concatenation of All Words
    You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.

You can return the answer in any order.

Example 1:

Input: s = “barfoothefoobarman”, words = [“foo”,”bar”]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are “barfoo” and “foobar” respectively.
The output order does not matter, returning [9,0] is fine too.
Example 2:

Input: s = “wordgoodgoodgoodbestword”, words = [“word”,”good”,”best”,”word”]
Output: []
Example 3:

Input: s = “barfoofoobarthefoobarman”, words = [“bar”,”foo”,”the”]
Output: [6,9,12]

Constraints:

1 <= s.length <= 104
s consists of lower-case English letters.
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] consists of lower-case English letters.

Answer 1

for 所有起始位置，然後每k個letter檢查，用hash來存出現的次數
可以優化的就是，當剩下的string數量已經不可能達到要求，就不用跑了
for i in xrange(len(s) - len(words) * l + 1):

Question 2

76. 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.

Answer 2

就是用l, r sliding window去做這件事。檢查是否valid要用O(1)的方法
這題用到了collections.Counter(t)
table.get(key, 0)
這些用法

我的寫法一直不成功，我想要在一個while裡面同時做r+=1 or l += 1，但是總是無法。如果init l, r = 0, 0，那r必須要到n，但是s[n]就會錯
如果init l, r = 0, -1，那就會發生s[-1]這樣也會錯。
如果出現這種，總是要馬超過或變-1得情況，也許就是你一個迴圈的循環訂錯了，像詳解訂的就是，一個迴圈的循環是r += 1然後l += 1直到不valid為止