Pythonで文字列を半単調にするために必要な最小の文字更新回数を求める方法

問題概要

小文字の英字のみで構成された、長さが偶数の文字列 s が与えられます。すべてのインデックス i（0 ≤ i < n/2）および j（n/2 ≤ j < n）の組み合わせに対して、次の3つの条件のいずれかひとつが一貫して成り立つようにするには、最低でも何文字を書き換える必要があるかを求めます。

• s[i] > s[j]
• s[i] < s[j]
• s[i] == s[j]

たとえば、入力が s = "pppxxp" の場合、答えは 1 になります。末尾の "p" を "x" に1文字だけ変更すれば、すべてのペアで条件 s[i] < s[j] が満たされるためです。

解法のアプローチ

この問題は、文字列を前半と後半に分割し、それぞれの文字の出現頻度をカウントすることで効率的に解けます。26種類の英小文字をそれぞれ「境界値（ピボット）」として試し、次の3つのパターンごとに変更不要な文字数を数え、必要な更新回数の最小値を求めます。

• 両側を同じ文字に揃える場合： 最も出現頻度の高い文字以外をすべて書き換えます。
• 前半 < 後半にする場合： ピボット以下の文字が前半にあり、ピボットより大きい文字が後半にあるものはそのまま保持できます。
• 前半 > 後半にする場合： ピボットより大きい文字が前半にあり、ピボット以下の文字が後半にあるものを保持します。

具体的な手順は以下の通りです。

• n := 文字列 s の長さ
• left := 前半部分の各文字の出現頻度を格納した辞書
• right := 後半部分の各文字の出現頻度を格納した辞書
• ans := n（初期値）
• 各英小文字 pivot について以下を実行する
  • ans := min(ans, n − left[pivot] − right[pivot])（全ペアが等しくなるケース）
  • good := left のうち c ≤ pivot の文字数の合計 ＋ right のうち c > pivot の文字数の合計とし、ans := min(ans, n − good)
  • good := left のうち c > pivot の文字数の合計 ＋ right のうち c ≤ pivot の文字数の合計とし、ans := min(ans, n − good)
• ans を返す

Pythonでの実装例

それでは、実際のコードを見て理解を深めましょう。

from collections import Counter
from string import ascii_lowercase

def solve(s):
    n = len(s)
    left = Counter(s[: n >> 1])
    right = Counter(s[n >> 1 :])

    ans = n
    for pivot in ascii_lowercase:
        # ケース1: すべてのペアで s[i] == s[j] となる場合
        ans = min(ans, n - left[pivot] - right[pivot])

        # ケース2: すべてのペアで s[i] < s[j] となる場合
        good = sum(left[c] for c in left if c <= pivot)
        good += sum(right[c] for c in right if c > pivot)
        ans = min(ans, n - good)

        # ケース3: すべてのペアで s[i] > s[j] となる場合
        good = sum(left[c] for c in left if c > pivot)
        good += sum(right[c] for c in right if c <= pivot)
        ans = min(ans, n - good)

    return ans

s = "pppxxp"
print(solve(s))

入力

"pppxxp"

出力

1

計算量について

このアルゴリズムでは、26種類の英小文字をピボットとしてループし、各ループ内で辞書の走査を行うため、時間計算量は O(26 × n)、つまり文字列長に対してほぼ線形時間となります。空間計算量も頻度辞書の分だけの O(n) で済むため、大きな入力に対しても十分に高速です。