使用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]

为了解决这个问题，我们将按照以下步骤进行 –

n：s的大小
left：包含s左半部分中每个字符频率的字典
right：包含s右半部分中每个字符频率的字典
ans：n
对于小写英文字母中的每个字符枢轴，进行
- ans：ans和（n-left [pivot] – right [pivot]）的最小值
- good：在（left [c]中存在的每个c）的所有元素的总和，如果c≤枢轴
- good：good + 在（right [c]中存在的每个c）的所有元素的总和，如果c> pivot
- ans：ans和（n-good）的最小值
- good：在（left[c]中存在的每个c）的所有元素的总和，如果c> pivot
- good：good + 在（right[c]中存在的每个c）的所有元素的总和，如果c≤枢轴
- 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))