【华为OD机试2023】递增字符串Python
题目描述：
定义字符串完全由 'A' 和 'B'组成，当然也可以全是'A'或全是'B'。如果字符串从前往后都是以字典序排列的，那么我们称之为严格递增字符串。
给出一个字符串s，允许修改字符串中的任意字符，即可以将任何的'A'修改成'B'，也可以将任何的'B'修改成'A'，求可以使s满足严格递增的最小修改次数。0<s的长度<100000。
输入描述：
输入一个字符串： "AABBA"
输出描述：
输出：1
修改最后一位得到AABBB。
示例1
输入：
AABBA
输出：
1
解题思路：
假设位置i为AB分界点，那么变换次数就是求i左边有多少B+i右边有多少A。从前遍历一边，算出各位置前有多少B，再从后遍历一边，算出各位置后有多少A。这两个值相加的最小值就是最小修改次数
st=input()
l=len(st)
left_b=[]
count_b=0
right_a=[]
count_a=0
for word in st:
if word=='B':
count_b+=1
left_b.append(count_b)
for word in st[::-1]:
if word=='A':
count_a+=1
right_a.append(count_a-1)
right_a=right_a[::-1]
min_change=l
for i in range(l):
change=left_b[i]+right_a[i]
min_change=min(min_change,change)
print(min_change)
类似资料：