動機

搞懂調整sliding window的條件

Problem

Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k.

 

Example 1:

Input: s = aaabb, k = 3Output: 3Explanation: The longest substring is aaa, as 'a' is repeated 3 times.

Example 2:

Input: s = ababbc, k = 2Output: 5Explanation: The longest substring is ababb, as 'a' is repeated 2 times and 'b' is repeated 3 times.

 

Constraints:

  • 1 <= s.length <= 104
  • s consists of only lowercase English letters.
  • 1 <= k <= 105

Sol: divide-and-conquer

無腦一直分割，一邊統計，一邊看有沒有不合的，就繼續分割

class Solution:
    def f(self,i,j):
        if j-i <= 1:
            return j-i if j-i >= self.k else 0
        else:
            tbl = Counter(self.s[i:j])
            for k in range(i,j):
                if tbl[self.s[k]] < self.k:
                    return max(self.f(i,k), self.f(k+1,j))
            return j-i if j-i >= self.k else 0
    def longestSubstring(self, s: str, k: int) -> int:
        self.s = list(s)
        self.k = k
        return self.f(0,len(s))

Sol2: sliding window

當初第一眼看到就想用，但是沒有用成，因為無法判斷，要怎麼往上漲，往右縮

根本原因是同時牽扯到

  1. 長度
  2. 字母數

長度當然是越長越好，但要怎麼判斷要讓windows停止生長與縮小，如果不限制字母數會無法判斷該漲還是該縮

所以要把其中一個固定下來，因為要找的是長度，所以變成固定字母數，以此為條件讓windows變化

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        s = list(s)
        ret = 0
        for maxDiffAlpha in range(1,len(set(s))+1):
            i = 0
            j = 0
            cnt = {}
            cntAlpha = 0
            howManyK = 0
            while j < len(s):
                if cntAlpha <= maxDiffAlpha:
                    if cnt.get(s[j],0) == 0:
                        cnt[s[j]] = 0
                        cntAlpha += 1
                    
                    cnt[s[j]] += 1
                    
                    if cnt[s[j]] == k:
                        howManyK += 1
                    
                    j += 1
                else:
                    if cnt[s[i]] == k:
                        howManyK -= 1
                    
                    cnt[s[i]] -= 1
                    
                    if cnt[s[i]] == 0:
                        cntAlpha -= 1
                    
                    i += 1
                if cntAlpha == maxDiffAlpha and cntAlpha == howManyK:
                    ret = max(ret, j-i)
        return ret