Longest Repeating Character Replacement
大文字の英字からなる文字列 s と整数 k が与えられます。s の位置を最大 k 個選び、それぞれの文字を任意の別の大文字に変更できます。
変更後に同じ文字が連続する部分文字列（隣り合う文字の並び）のうち、最も長いものの長さを返してください。
関数
- sstring
- 大文字の文字列
- kinteger
- 変更できる文字の最大数
- 戻り値integer
- 作成できる、同じ文字が最も長く連続する部分文字列の長さ
制約
1 ≤ s.length ≤ 5 × 104sには英語の大文字のみが含まれます。0 ≤ k ≤ s.length
例
- 入力
- s = "BAAACAB"k = 1
- 出力
- 5
- 説明
CをAに変更すると、インデックス1から5はAAAAAになります。6文字のウィンドウはどちらもBとCを含むため、2回変更する必要があります。
- 入力
- s = "AABBBAB"k = 2
- 出力
- 6
- 説明
- インデックス1から6には
ABBBABがあり、2つのAを変更するとBBBBBBになります。文字列全体には7文字のうちBが4つしかないため、3つ変更する必要があります。
- 入力
- s = "WXYZ"k = 0
- 出力
- 1
- 説明
- 変更が許されないため、答えは文字列内にすでにある最長の連続部分です。どの文字も隣り合う文字と異なるため、その連続部分は1文字です。
発展問題
26個の大文字ではなく、sに任意の文字を格納できる場合、何が変わりますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
固定された部分文字列について、他の各文字はどの文字に変わるべきで、そのために何回変更する必要がありますか？
部分文字列の長さから最も頻出する文字の数を引いた値が
k以下の場合、その部分文字列は到達可能です。文字列上で両端を前方に移動させて、この条件を満たす最長のウィンドウを見つけましょう。26 個のカウントと最大カウント
topを保持します。右側に文字を 1 つ追加し、ウィンドウを変更する必要がある回数がkを超える場合は、長さを保つために左側の文字を 1 つ削除します。ウィンドウを縮める必要はなく、topを減らす必要もありません。
解説
部分文字列で最も多く出現する文字を残し、それ以外を変更します。長さが len で、最頻文字が top 回出現する部分文字列では、len - top 回の変更が必要です。スライディングウィンドウを使うと、1回の走査で len - top ≤ k を満たす最長の部分文字列を見つけられます。ウィンドウを縮める必要はなく、top が減ることもないためです。
すべての部分文字列を確認する
正しいが、最大のテストでは終わらない
考え方
各開始位置について、終端を1文字ずつ伸ばし、文字ごとのカウントとtopを更新して、len - top ≤ kを確認します。新しい部分文字列ごとに必要なのは新たなカウントではなく1回の更新だけで、すべての部分文字列をチェックするため、到達可能な最長のものを見逃すことはありません。
長さ n の文字列には約 n²/2 個の部分文字列があります。n = 5 × 10^4 の場合、チェック回数は 1.25 × 10^9 回です。
アルゴリズム
bestを0に設定します。- 各開始インデックスについて、26個のカウントと
topを0にリセットします。 endを開始位置から最後のインデックスまで移動します。s[end]をその文字のカウントに加え、そのカウントが現在最も高ければtopを増やします。end - start + 1 - top ≤ kの場合、長さがbestを上回ればその長さを保存します。bestを返します。
def characterReplacement(s, k):
n = len(s)
best = 0
for start in range(n):
count = [0] * 26 # letters in s[start..end]
top = 0 # count of the most common letter there
for end in range(start, n):
c = ord(s[end]) - ord('A')
count[c] += 1
top = max(top, count[c])
# Every letter that is not the most common one must change.
if end - start + 1 - top <= k:
best = max(best, end - start + 1)
return best対象の各文字につき1つのスライディングウィンドウ
考え方
まず最後の文字を選びます。実行結果がすべて A になるなら、k 文字以下の A 以外の文字を含む最長の部分文字列を求めます。
文字列上で right を進め、ウィンドウ内の対象以外の文字を数えます。個数が k を超えたら、再び k になるまで left を進めます。コストが大きすぎるウィンドウは、広げてもコストが大きすぎるままなので、left が戻ることはありません。また、各 right について、その位置で終わる最長の条件を満たすウィンドウになります。
26 個すべての文字について実行し、最良の結果を保持します。最大 5 × 10^4 文字に対する線形走査を 26 回行います。アルファベットが小さいため、全体の計算量は O(n) に収まります。
アルゴリズム
AからZまでの各対象文字について、left = 0、others = 0でウィンドウを開始します。- 文字列上で
rightを進めます。s[right]が対象文字でない場合は、othersに1を加えます。 others > kの間、leftを前に進め、ウィンドウから出る文字が対象文字でない場合は1を引きます。right - left + 1がbestを上回る場合、その値を保存します。- 26文字すべてを処理した後、
bestを返します。
def characterReplacement(s, k):
best = 0
for target in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
left = 0
others = 0 # letters in s[left..right] that are not target
for right in range(len(s)):
if s[right] != target:
others += 1
# Too many letters to change: drop letters from the left.
while others > k:
if s[left] != target:
others -= 1
left += 1
best = max(best, right - left + 1)
return best決して縮まないウィンドウ
考え方
ウィンドウ内の各文字の個数を26個分管理し、最も多い個数をtopとします。s[right]を追加したとき、ウィンドウの変更コストが高くなりすぎる場合は、左端の文字を1つ取り除きます。ウィンドウはスライドして長さを保ちます。記録を更新できるのは、より長いウィンドウだけだからです。そうでなければ、ウィンドウは1つ分伸びます。その長さは常にここまでの最長なので、答えはn - leftです。
文字がウィンドウから外れても、実際の個数より大きくなったとしても、topはそのままにします。スライド後の長さはちょうどtop + kなので、ウィンドウを伸ばすには、ある文字がtop + 1回出現する必要があり、その時点でtopも増えます。古いままのtopが引き起こすのはウィンドウのスライドだけであり、スライドによって記録を失うことはありません。
k = 1のとき、BAAACABではBAAACを作るのに2回の変更が必要なので、ウィンドウはスライドしてAAACになります。次のAによってtopは4に上がり、ウィンドウは長さ5のAAACAに伸びます。
アルゴリズム
- 26 個のカウントと、
left = 0、top = 0を保持します。 rightを文字列上で進めます。s[right]をそのカウントに加え、そのカウントがこれまでより大きくなった場合はtopを増やします。right - left + 1 - top > kの場合、カウントからs[left]を取り除き、leftを 1 つ進めます。topは決して減らしません。- 最終的なウィンドウの長さ
n - leftを返します。
def characterReplacement(s, k):
count = [0] * 26 # letters inside the window s[left..right]
left = 0
top = 0 # the highest count any letter has reached in a window
for right in range(len(s)):
c = ord(s[right]) - ord('A')
count[c] += 1
top = max(top, count[c])
# Needs more than k changes: slide the window instead of growing it.
if right - left + 1 - top > k:
count[ord(s[left]) - ord('A')] -= 1
left += 1
# The window only grew when a longer valid substring was found.
return len(s) - left
落とし穴と境界ケース
- 最長の連続部分に
kを加える。k = 3のAAABでは6となり、文字列の長さを超えてしまう。k = 1のBAAACABでは4となるが、Cを変更すると2つの連続部分がつながり、5になる。 - 最も多く含まれる文字ではなく、ウィンドウの先頭の文字に合わせて変更回数を数える。
BAAAで必要な変更は3回ではなく1回。 whileでウィンドウを縮め、実際の最大値を再計算するループでn - leftを返す。このウィンドウは短くなるため、別にbestを保持する。- ウィンドウの長さを
right - leftで求める。両端ともウィンドウに含まれるため、1を足す。
よくある質問3
Longest Repeating Character Replacement の時間計算量はどのくらいですか？
1つのウィンドウで解く方法は、n を s の長さとして、O(n) 時間で実行されます。right は各文字を1回ずつ確認し、left は各ステップで最大1回移動します。追加の領域は O(1) で、26個のカウントといくつかの整数を使用します。
これは「文字が重複しない最長部分文字列」とどう違いますか？
どちらも文字列上で両端を動かしますが、有効なウィンドウの条件は異なります。前者では文字が重複してはいけないため、重複がなくなるまでウィンドウを縮めます。こちらでは、ウィンドウの長さから最頻出文字の出現回数を引いた値が k 以下であればよいため、ウィンドウは長さを固定したままスライドできます。
この問題は二分探索で解決できますか？
はい。長さ L の部分文字列に到達可能なら、その中にあるそれより短い部分文字列もすべて到達可能なので、L を二分探索できます。各 L について、その長さの固定ウィンドウをスライドさせ、変更が k 回以下で済む位置があるかどうかを確認します。これは O(n log n) で、1 つのウィンドウだけを使う方法より遅くなります。
def characterReplacement(s, k):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
s = "BAAACAB" k = 1
期待される出力
5