Python程式：查詢使字串半單調所需的更新次數

假設我們有一個長度為偶數的小寫字串s。我們需要找到需要更新的字元的最小數量，以便以下三個條件之一對於所有i都滿足，其中0 ≤ i < n/2 且 j，n/2 ≤ j < n −

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

因此，如果輸入類似於 s = "pppxxp"，則輸出將為 1，因為如果我們將最後一個 "p" 更改為 "x"，則可以滿足條件 s[i] < s[j]

為了解決這個問題，我們將遵循以下步驟：

  • n := s的大小
  • left := 包含s左半部分中每個字元頻率的字典
  • right := 包含s右半部分中每個字元頻率的字典
  • ans := n
  • 對於每個小寫英文字母字元pivot，執行以下操作：
    • ans := ans 和 (n - left[pivot] - right[pivot]) 的最小值
    • good := (left[c] 中所有元素的總和，對於left中的每個c，如果c <= pivot)
    • good := good + (right[c] 中所有元素的總和，對於right中的每個c，如果c > pivot)
    • ans := ans 和 (n - good) 的最小值
    • good := (left[c] 中所有元素的總和，對於left中的每個c，如果c > pivot)
    • good := good + (right[c] 中所有元素的總和，對於right中的每個c，如果c <= pivot)
    • ans := ans 和 (n - good) 的最小值
  • 返回 ans

示例

讓我們看看以下實現以更好地理解：

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

更新於: 2021年10月18日

111 次瀏覽

開啟你的 職業生涯

完成課程獲得認證

開始學習
廣告