[リートコード] 0424. 最長繰り返し文字の置換

Python、C++、JavaScript、SQL、TypeScript の多様な LeetCode ソリューションを探索してください。面接の準備、学習、複数のプログラミング言語でのコードの練習に最適です。 Github リポジトリリンク

中くらい

文字列が与えられます s そして整数 k文字列の任意の文字を選択し、他の大文字の英語文字に変更できます。この操作は最大で k 回。

戻る 上記の操作を実行した後に得られる同じ文字を含む最長の部分文字列の長さ.

例 1:

入力： s = "ABAB"、k = 2
出力： 4
説明： 2 つの「A」を 2 つの「B」に置き換えます (またはその逆)。

例 2:

入力： s = "AABABBA"、k = 1
出力： 4
説明： 真ん中の「A」を「B」に置き換えて、「AABBBBA」を作ります。部分文字列「BBBB」には、最も長い繰り返し文字があり、4 です。この答えを得るには、他の方法もあるかもしれません。

制約:

1 <= s.length <= 10 ⁵
s 大文字の英語のみで構成されます。
0 <= k <= s.長さ

パイソン

				
					# 時間計算量: O(n) # 空間計算量: O(1) from collections import defaultdict class Solution: def characterReplacement(self, s: str, k: int) -> int: result = 0 left = right = 0 freq = defaultdict(int) mostFreqChar = 0 for right in range(len(s)): freq[s[right]] += 1 mostFreqChar = max(mostFreqChar, freq[s[right]]) if right - left + 1 - mostFreqChar > k: freq[s[left]] -= 1 left += 1 result = max(result, right - left + 1) return result s = "AABABBA" k = 1 print(Solution().characterReplacement(s, k))

中くらい

パイソン

関連記事