スライディングウィンドウで k 枚まで塗り替えて同じ色の最長の並びを作る

スライディングウィンドウ問題 101

色を英大文字で表したタイルの並びで、k 枚まで塗り替えてよいとき、同じ色が続く並びを最も長くします。窓の長さから最も多い色の数を引いた数が k 以下、を保つスライディングウィンドウの練習です。

海外で定番の問題リスト 4 本には入っていません

問題

壁に 1 列に貼ったタイルの色を、英大文字の文字列 s で受け取ります。s[i] が左から i 番目のタイルの色です。タイルは多くて k 枚まで、好きな色に塗り替えられます。

塗り替えたあと、同じ色のタイルが途切れずに続く部分を、最も長くて何枚にできるかを返す関数を書いてください。

塗り替える色は、英大文字のどれでもかまいません。塗り替えは k 枚より少なくてもかまいません
s の長さは 1 以上 100000 以下で、A から Z の英大文字だけでできています
k は 0 以上、s の長さ以下です

入力と出力の例

例 1

左から 3 枚目から最後までの "GRGGGR" は、G が 4 枚、R が 2 枚です。R の 2 枚を G に塗れば、G が 6 枚続きます。

s = "RRGRGGGR" k = 2

例 2

塗り替えられません。もとから続いている最後の "XX" の 2 枚がいちばん長い並びです。

s = "XYZXX" k = 0

例 3

4 枚とも色が違いますが、4 枚まで塗り替えられるので、全部を同じ色にできます。

s = "ABCD" k = 4

面接での聞かれ方

面接では、文字列の言葉で渡されることがよくあります。

「k 文字まで置き換えて、同じ文字が続く最長の部分文字列の長さを求めてください」
「置き換える先の文字は、何でもいいですか？」と、範囲を自分から確かめるかを見られます
書き終えたあとに「最も多い文字の数を、窓が縮むときに減らさなくていいのはなぜですか？」と聞かれることもあります

窓の中で「どの色にそろえるか」を考えると迷いますが、いちばん多い色にそろえるのが最も塗り替えが少ない、と気づけば、条件は 1 つの式になります。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

まず考える手順

段 1

1 つの区間を、全部同じ色にできるかを考えます。塗り替えが最も少なく済むのは、区間の中でいちばん多い色にそろえるときです。塗り替える枚数は「区間の長さ − いちばん多い色の枚数」で、これが k 以下ならそろえられます。

段 2

素直に書くなら、全部の区間について段 1 を確かめます。始まりを決めて終わりを伸ばしながら色の数を足していけば、全体で O(n²) です。長さ 10 万では遅すぎます。

段 3

左右の端を持つ窓にします。右の端を 1 枚ずつ伸ばし、色の数を足し、いちばん多い色の枚数 top を更新します。窓の長さから top を引いた数が k を越えたら、左の端を 1 枚進めて、出ていくタイルの色の数を引きます。

段 4

ここで 2 つの工夫をします。1 つは、k を越えたとき左の端を 1 枚だけ進め、窓の長さを前と同じに保つことです。答えより短い窓を調べる意味は無いので、窓は縮めずに横へずらせば足ります。もう 1 つは、top を減らさないことです。top が昔の値のままだと窓を正しく判定できないことがありますが、答えが伸びるのは top がいまの値を越えたときだけなので、答えは変わりません。こうすると、色の数を数え直す手間が要りません。

解答

Python

from collections import Counter


def longest_repaint(s, k):
    count = Counter()
    lo = 0
    top = 0
    best = 0
    for r, c in enumerate(s):
        count[c] += 1
        top = max(top, count[c])
        size = r - lo + 1
        if size - top > k:
            count[s[lo]] -= 1
            lo += 1
            size -= 1
        best = max(best, size)
    return best

JavaScript

function longestRepaint(
  s,
  k
) {
  const count = {};
  const n = s.length;
  let lo = 0;
  let top = 0;
  let best = 0;
  for (let r = 0; r < n; r++) {
    const c = s[r];
    count[c] ??= 0;
    const got = ++count[c];
    top = Math.max(top, got);
    let size = r - lo + 1;
    if (size - top > k) {
      count[s[lo]]--;
      lo++;
      size--;
    }
    best = Math.max(best, size);
  }
  return best;
}

Go

func longestRepaint(
	s string,
	k int,
) int {
	var count [26]int
	lo, top, best := 0, 0, 0
	for r := 0; r < len(s); r++ {
		c := s[r] - 'A'
		count[c]++
		top = max(top, count[c])
		size := r - lo + 1
		if size-top > k {
			count[s[lo]-'A']--
			lo++
			size--
		}
		best = max(best, size)
	}
	return best
}

lo が窓の左の端、r が右の端、size が窓の長さです。条件を越えたら左の端を 1 つだけ進めるので、窓の長さは伸びるか、前と同じかのどちらかで、縮みません。Go は色が英大文字の 26 種類だけなので、長さ 26 の配列で数えています。

計算量

時間は O(n) です。右の端も左の端も、それぞれ前へ 1 回ずつしか進みません
使う記憶は O(1) です。色の数を数えるのは英大文字の 26 種類ぶんだけです
段 2 の全部の区間を確かめる書き方は、時間が O(n²) です

よくある間違い

窓の中の最初の色や、右の端の色にそろえると決める。いちばん多い色にそろえるのが最も少ない塗り替えです。例 1 で R にそろえると考えると、6 枚の並びを見落とします
窓の長さを r - lo で数える。 両端を含むので + 1 が要ります。1 文字の "A" で 1 になるかを確かめると気づけます
top を減らそうとして、毎回 26 色を数え直す。 答えは合いますが手間が増えます。減らさなくてよい理由を説明できるようにしておきます
塗り替えの数を「窓の中の違う色の数」で数える。 "GRGGGR" の違う色は 2 種類ですが、塗り替えるのは R の 2 枚です。種類ではなく枚数で数えます

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def longest_repaint(s: str, k: int) -> int:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(longest_repaint("RRGRGGGR", 2))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します