Pythonで文字列を半単調にするために必要な更新の数を見つけるプログラム

• n：=sのサイズ
• left：=sの左半分からの各文字の頻度を含む辞書
• right：=sの右半分からの各文字の頻度を含む辞書
• ans：=n
• 小文字の英字でピボットする各文字について、
  • ans：=最小のansおよび（n-左[ピボット]-右[ピボット]）
  • good：=（c<=ピボットの場合は左の各cのleft[c]）に存在するすべての要素の合計
  • good：=good + c>ピボットの場合、右の各cについてright[c]に存在するすべての要素の合計
  • ans：=最小のansおよび（n-良い）
  • good：=c>ピボットの場合、左の各cのleft[c]に存在するすべての要素の合計
  • good：=good + c <=ピボットの場合、右の各cについてright[c]に存在するすべての要素の合計
  • ans：=最小のansおよび（n-良い）
• 回答を返す

例

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

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:
      ans = min(ans, n - left[pivot] - right[pivot])

      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)

      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