題目鏈接：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è)問題：

1. 遞歸函數(shù)的物理意義是什么？
2. 遞歸的終止條件是什么？
3. 對(duì)于當(dāng)前層來說，子問題是什么？

對(duì)于這道題，也可以通過回答這三個(gè)問題來明確遞歸思路。

1. 設(shè)計(jì)的遞歸函數(shù) longestSubstring(s string, k int) int，它的物理意義即題意：給定一個(gè)字符串s，找到長度最長的滿足條件的子字符串，該子字符串的每一種字符都出現(xiàn)了k次以上。
2. 終止條件是：1. s 的長度小于 k，不存在符合條件的子串，返回0；2. 當(dāng)前 s 即滿足條件，即 s 中每個(gè)字符都出現(xiàn) k 次以上，返回 s 的長度。
3. 將當(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為字符串的長度，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)