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 次浏览

开启你的 职业生涯

完成课程获得认证

开始学习
广告