数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python程序：查找使字符串平衡所需的最小删除次数
假设我们有一个字符串s，其中只有两个字符's'和't'。我们可以删除s的任意数量的字符以使字符串平衡。如果不存在一对索引(i,j)使得i < j且s[i] = 't'且s[j]= 's'，则可以说s是平衡的。我们必须找到使s平衡所需的最小删除次数。
因此，如果输入类似于s = "sststtst"，则输出将为2，因为我们可以删除索引2和6处的字符（"sststtst"变为"sssttt"），或者删除索引3和6处的字符（"sststtst"变为"sstttt"）。
为了解决这个问题，我们将遵循以下步骤：
cum_b := 0
count_a := 字符's'在s中的数量
ans := 无穷大
对于s中的每个x，执行：
如果x与"s"相同，则
count_a := count_a - 1
ans := ans 和 (cum_b + count_a) 的最小值
否则，
cum_b := cum_b + 1
ans := ans 和 (cum_b - 1 + count_a) 的最小值
返回 ans
示例
让我们看看下面的实现，以便更好地理解：
def solve(s):
cum_b = 0
count_a = s.count("s")
ans = float("inf")
for x in s:
if x == "s":
count_a-=1
ans = min(ans,cum_b + count_a)
else:
cum_b+=1
ans = min(ans,cum_b-1 + count_a)
return ans
s = "sststtst"
print(solve(s))
输入
"sststtst"
输出
2
更新于：2021年10月6日
492 次浏览
广告