動機

lee215太神啦!!

Problem

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

 

Example 1:

Input: s = ABAB, k = 2Output: 4Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input: s = AABABBA, k = 1Output: 4Explanation: Replace the one 'A' in the middle with 'B' and form AABBBBA.The substring BBBB has the longest repeating letters, which is 4.

 

Constraints:

  • 1 <= s.length <= 105
  • s consists of only uppercase English letters.
  • 0 <= k <= s.length

Sol

當初腦袋撞到，一直想用dp去做，但做下去會發現如果要遞迴勢必要知道要換成什麼字，這樣維度就會上升

之後才想起來sliding windows 先加大到剛好出事，之後再扣一位

def legal(tbl,k):
    big = tbl.most_common(1)[0][1]
    ks = sum(tbl.values())
    return ks-big <= k
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        ret,a,b,tbl = 0,0,1,Counter(s[0])
        while a < len(s):
            # expand
            while b < len(s) and legal(tbl,k):
                tbl.update(s[b])
                ret = max(ret, b-a) # 只要是合法的地方都要收集值 "AAAB" 0
                b += 1
            if b < len(s):
                tbl.subtract(s[b-1])
                b -= 1
            print(a,b)
            if legal(tbl,k):
                ret = max(ret, b-a)
            tbl.subtract(s[a])
            a += 1
        return ret

之後看到了很神的寫法，同樣用一個dict紀錄windows的內容物 總長度 = 最多的字 + 其他字而其他字的長度不能大於k

之後就是一路往前，當出事是就移動一格

為什麼不是移動到合法為止? 就算是合法也不會比之前看到的長，如果之後有合法的，也會比現在調整完的合法長

另外，合法的可能性很大，就算真的違法，只要往後找到一堆一樣的就直接合法了!!

這邊還有一個地方是它是在違法時才更新!!

太聰明啦!!

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        start, res = 0, 0
        dict = collections.defaultdict(int)
        for i in range (len(s)):
            dict[s[i]] += 1
            if max(dict.values()) < i-start+1-k:
                res = max(res, i-start)
                dict[s[start]] -= 1
                start += 1
        return max(res, len(s)-start)

之後寫了兩個版本

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        ret,a,tbl = 0,0,defaultdict(int)
        for b in range(len(s)):
            tbl[s[b]]+=1
            if max(tbl.values()) < b-a+1-k:
                ret = max(ret, b-a)
                tbl[s[a]]-=1
                a += 1
        return max(ret,b-a+1)

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        ret,a,tbl = 0,0,Counter()
        for b in range(len(s)):
            tbl.update(s[b])
            if max(tbl.values()) < b-a+1-k:
                ret = max(ret, b-a)
                tbl.subtract(s[a])
                a += 1
        return max(ret,b-a+1)

Counter的硬是比dict慢一倍以上