假设我们有一个字符串 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”)。
让我们看看以下实现以获得更好的理解 -
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