Pythonで文字列をバランスさせるための最小削除数を求めるプログラム

問題の概要

's' と 't' の2種類の文字のみで構成された文字列 s があるとします。この文字列を「バランスの取れた状態」にするために、任意の数の文字を削除することができます。

ここで、文字列 s がバランスしているとは、i < j を満たすインデックスのペア (i, j) であって、s[i] = 't' かつ s[j] = 's' となるものが存在しない状態を指します。つまり、't' の後に 's' が現れることがない状態です。私たちの目的は、s をバランスさせるために必要な最小の削除回数を求めることです。

入力例

例えば、入力が s = "sststtst" の場合、出力は 2 になります。これは次のいずれかの操作で文字列をバランスさせられるからです。

• インデックス 2 と 6 の文字を削除し、"sststtst" → "sssttt" にする
• インデックス 3 と 6 の文字を削除し、"sststtst" → "sstttt" にする

解法のアプローチ

この問題は、文字列をある位置で分割したときに、「分割位置より前にある 't' の個数」と「分割位置より後ろにある 's' の個数」の合計が、その分割位置における削除数になるという性質を利用します。すべての分割位置についてこの値を計算し、その最小値を答えとすればよいのです。

具体的には、以下の手順で解きます。

• cum_b := 0(それまでに登場した 't' の個数)
• count_a := 文字列 s に含まれる 's' の総数
• ans := 無限大(初期値)
• s 内の各文字 x について以下を繰り返す
  • x が "s" の場合:
    • count_a := count_a - 1(現在位置より後ろの 's' の個数に更新)
    • ans := ans と (cum_b + count_a) の小さい方
  • それ以外の場合:
    • cum_b := cum_b + 1
    • ans := ans と (cum_b - 1 + count_a) の小さい方
• ans を返す

実装例(Python)

理解を深めるために、以下の実装を見てみましょう。

def solve(s):
   cum_b = 0
   count_a = s.count("s")
   ans = float("inf")
   for x in s:
      if x == "s":
         count_a -= 1
         ans = min(ans, cum_b + count_a)
      else:
         cum_b += 1
         ans = min(ans, cum_b - 1 + count_a)
   return ans

s = "sststtst"
print(solve(s))

入力

"sststtst"

出力

2

計算量について

このアルゴリズムは文字列を一度だけ走査するため、時間計算量は O(n)、追加の記憶領域も定数個の変数だけで済む O(1) となります。文字列の長さが大きくなっても効率的に動作する点が魅力です。