Pythonで最大k回の置換により同じ数が並ぶ最長の部分リストの長さを求める方法

問題概要

リスト nums と整数 k が与えられたとします。ここで「1回の操作」とは、リスト内の任意の要素の値を別の値に書き換えることを指します。最大 k 回までの操作を行った後、同じ数が繰り返し並んでいる 最長の部分リスト(連続する区間)の長さを求めるのが目的です。

入力例

たとえば、nums = [8, 6, 6, 4, 3, 6, 6]、k = 2 が入力された場合、出力は 6 になります。

理由は次のとおりです。値 4 と 3 を 6 に書き換えることで、配列は [8, 6, 6, 6, 6, 6, 6] となり、すべてが 6 で構成される部分リストの長さは 6 になります。

解法のアプローチ:スライディングウィンドウ

この問題はスライディングウィンドウ(尺取り法)を使うことで、線形時間 O(n) で効率的に解けます。ウィンドウ内で最も多く出現している数の出現回数を max_count として管理し、「ウィンドウ幅 − max_count > k」となったタイミングでウィンドウの左端を縮めていくのがポイントです。

具体的な手順

• nums が空の場合は 0 を返します。
• num_count:各数値の出現回数を記録するマップ(defaultdict)を用意します。
• max_count := 0:ウィンドウ内の最多出現回数を初期化します。
• start := 0:ウィンドウの左端インデックスです。
• 各インデックス end とその値 num に対して以下を繰り返します。
  • num_count[num] を 1 増やします。
  • max_count を必要に応じて更新します。
  • end - start + 1 > max_count + k の場合、左端の要素のカウントを 1 減らし、start を 1 進めます。
• 最後に end - start + 1 を返します。

この方法では、ウィンドウは一度も縮小して「答えより短くなる」ことがないため、常にこれまでの最良の長さ以上が保持され、正しい結果が得られます。

Pythonでの実装例

from collections import defaultdict
def solve(nums, k):
    if not nums:
        return 0

    num_count = defaultdict(int)
    max_count = 0
    start = 0

    for end, num in enumerate(nums):
        num_count[num] += 1
        max_count = max(max_count, num_count[num])
        if end - start + 1 > max_count + k:
            num_count[nums[start]] -= 1
            start += 1
    return end - start + 1

nums = [8, 6, 6, 4, 3, 6, 6]
k = 2
print(solve(nums, k))

入力

[8, 6, 6, 4, 3, 6, 6], 2

出力

6

計算量

リストを一度だけ走査するため、時間計算量は O(n)、出現回数を記録するマップが必要とする空間計算量も O(n) となります(n はリストの長さ)。素朴な全探索(O(n²) 以上)に比べて大幅に高速であり、大きな入力にも対応できます。