題目鏈接：395
解題思路
對(duì)于substring变姨、subarray這種求子集類的問題谜诫，常用的做法有兩種：一是遞歸，二是滑動(dòng)窗口急膀。
遞歸天生就適合解決這類問題画株，因?yàn)樗褪峭ㄟ^解決“子集”從而來解決“父集”的瀑志。
滑動(dòng)窗口則是由于窗口內(nèi)的所有元素其實(shí)就是一個(gè)“子集”，只不過通過某種具有“單調(diào)性”的策略將策略范圍內(nèi)的子集遍歷了一遍污秆，從而找到答案劈猪。滑動(dòng)窗口相比于遞歸擁有更好的時(shí)間良拼、空間復(fù)雜度战得，但它的使用限制則比遞歸多，只能解決具有“單調(diào)性”策略的問題庸推。
根據(jù)官方題解常侦，似乎可以用滑動(dòng)窗口解決浇冰，但是我沒有理解具體的做法。
而使用遞歸解決問題的時(shí)候聋亡，最重要的是回答三個(gè)問題：
- 遞歸函數(shù)的物理意義是什么肘习？
- 遞歸的終止條件是什么？
- 對(duì)于當(dāng)前層來說坡倔，子問題是什么漂佩？
對(duì)于這道題，也可以通過回答這三個(gè)問題來明確遞歸思路罪塔。
- 設(shè)計(jì)的遞歸函數(shù) longestSubstring(s string, k int) int投蝉，它的物理意義即題意：給定一個(gè)字符串s，找到長(zhǎng)度最長(zhǎng)的滿足條件的子字符串征堪，該子字符串的每一種字符都出現(xiàn)了k次以上瘩缆。
- 終止條件是：1. s 的長(zhǎng)度小于 k，不存在符合條件的子串佃蚜，返回0庸娱；2. 當(dāng)前 s 即滿足條件，即 s 中每個(gè)字符都出現(xiàn) k 次以上谐算，返回 s 的長(zhǎng)度涌韩。
- 將當(dāng)前字符串根據(jù)不符合條件的字符進(jìn)行分割，分割后的不包含非法字符的子串即為新的子問題氯夷，而當(dāng)前問題的答案即為所有子問題的答案的最大值臣樱。
根據(jù)以上分析，可以寫出代碼：
// use recursion
// recursion rule: give a string s, return the longest substring's length that is satisfed
func longestSubstring(s string, k int) int {
// Base case
if len(s) < k {
return 0
}
// scan the string, use two maps to record info
// m1: key: char; val: appearing times
// valid: record satisfied character, key: char; val: bool
m1 := make(map[byte]int)
valid := make(map[byte]bool)
for i := range s {
ch := s[i]
count, ok := m1[ch]
if !ok {
m1[ch] = 1
} else {
m1[ch] = count + 1
}
// 滿足條件了腮考，加入 valid map 中
if m1[ch] >= k {
valid[ch] = true
}
}
// all characters are satisfied
if len(m1) == len(valid) {
return len(s)
}
// use sliding window to discard invalid character and split the string
// all characters in substring between [left, right) are valid, do dfs on this substring
left := 0
right := 0
maxLength := 0
for right < len(s) {
// find left bound
for left < len(s) && !valid[s[left]] {
left++
}
// refresh right bound
if right < left {
right = left
}
// find right bound
for right < len(s) && valid[s[right]] {
right++
}
// record ans
length := longestSubstring(s[left:right], k)
maxLength = max(maxLength, length)
// refresh left bound
left = right
}
return maxLength
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
時(shí)間復(fù)雜度：O(N * 26)雇毫。N為字符串的長(zhǎng)度，26為字符集的個(gè)數(shù)踩蔚，本題中字符為所有小寫字母棚放，即26個(gè)。由于每一次遞歸都能完全去除一種字符（即一種小寫字母）馅闽，因此遞歸最深有26層飘蚯，每一層最多遍歷N個(gè)元素，因此時(shí)間復(fù)雜度是O(N * 26)
空間復(fù)雜度：O(26 * 26)福也。由于最深能夠遞歸26層局骤，每一層又開辟了map，該map最多存26個(gè)鍵值對(duì)暴凑，即一個(gè)map O(26)的空間復(fù)雜度峦甩，因此總共的空間復(fù)雜度是 O(26 * 26)
