Pythonで文字列のバランスをとるための最小限の削除を見つけるプログラム

's'と't'の2文字だけの文字列sがあるとします。 sの任意の数の文字を削除して、文字列のバランスをとることができます。 i

したがって、入力がs ="sststtst"の場合、出力は2になります。これは、インデックス2および6（"sststtst"から"sssttt"）の文字を削除するか、インデックス3および6（"sststtst"から"sstttt"）。

これを解決するには、次の手順に従います-

• cum_b：=0

• count_a：=s内の文字's'の数

• ans：=無限大

• sのxごとに、実行します

  • xが「s」と同じ場合

    • count_a：=count_a-1

    • ans：=ansの最小値と（cum_b + count_a）

  • それ以外の場合

    • cum_b：=cum_b + 1

    • ans：=ansの最小値と（cum_b-1 + count_a）

• ansを返す

例

理解を深めるために、次の実装を見てみましょう-

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