NeetCode 150 [Sliding Window]:medium 2/3

NeetCodeのSolutionを書いていく

Longest Repeating Character Replacement

問題概要

大文字のアルファベットの文字列sと、整数kが与えられます。
k個までの文字を選択できます。それらを任意の大文字アルファベットに置換できます。
最大k回の置換を実施した後、ただ一つの文字を含むサブ文字列の最大長を返しなさい。

例

Input: s = "XYYX", k = 2
Output: 4

Input: s = "AAABABB", k = 1
Output: 5

sは1以上1000以下。
kは0以上s以下。

計算量：O(n) nは文字列長
メモリ：O(m) mはユニークな文字列の数

メモ

相変わらずわからない。
ヒントもいまいち適切じゃない感じがする。

• 原文

It is always optimal to replace characters with the most frequent character in the string. Why? Because using the most frequent character minimizes the number of replacements required to make all characters in the string identical. How can you find the number of replacements now?

• google 翻訳

文字を文字列内で最も頻繁に使用される文字に置き換えることが常に最適です。なぜでしょうか? 最も頻繁に使用される文字を使用すると、文字列内のすべての文字を同一にするために必要な置換回数が最小限に抑えられるためです。置換回数はどのようにして確認できますか?

「文字を文字列内で最も頻繁に使用される文字に置き換えることが常に最適です。」は明らかに間違っている。
例えば
Input: s = "AAABBABBA", k = 1
の場合
Output: 5
となりこの場合のサブ文字列は"最も頻繁に使用されているAではなくB。

おそらく「文字をサブ文字列内で最も頻繁に使用される文字に置き換えることが常に最適です。」が正しいと思われる。

自分の回答は以下！ごちゃごちゃ！

from collections import defaultdict


class MySolution:
    def characterReplacement(self, s: str, k: int) -> int:
        character_nums: defaultdict[str, int] = defaultdict(lambda: 0)
        l = r = 0
        max_len = 0
        for n in range(len(s)):
            character_nums[s[r]] += 1
            length = r - l + 1
            if len(character_nums) == 1:
                max_len = character_nums[s[l]]
            else:
                temp = character_nums.copy()
                m = max(character_nums, key=character_nums.get)
                del temp[m]
                if sum(temp.values()) <= k:
                    if max_len < length:
                        max_len = length
                else:
                    character_nums[s[l]] -= 1
                    l += 1
            r += 1
        return max_len

模範回答は以下、スマート！

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = {}  # 配列番号毎の出現回数を保持
        res = 0  # 最終的に返す結果

        l = 0  # 左のポインタ
        maxf = 0  # 各文字の出現回数の最大値を保持
        for r in range(len(s)):  # 右を動かしていく
            count[s[r]] = 1 + count.get(s[r], 0)  # 右の文字の出現回数に1を足す
            
            # 各文字の出現回数の最大値を保持。ここがポイント。サブ文字列内の最大文字長を判断基準にする
            maxf = max(maxf, count[s[r]])

            # ウィンドウ長から右の文字の出現回数を引く
            while (r - l + 1) - maxf > k:
                count[s[l]] -= 1  # 左の文字から出現回数を減らして
                l += 1  # 左のポインタを進める
            res = max(res, r - l + 1)

        return res