跳转至

1653. 使字符串平衡的最少删除次数#

问题描述#

给你一个字符串 s ，它仅包含字符 'a' 和 'b'​​​​ 。

你可以删除 s 中任意数目的字符，使得 s 平衡 。我们称 s 平衡的 当不存在下标对 (i,j) 满足 i < j 且 s[i] = 'b' 同时 s[j]= 'a' 。

请你返回使 s 平衡 的 最少 删除次数。

 

示例 1：


输入：s = "aababbab"
输出：2
解释：你可以选择以下任意一种方案：
下标从 0 开始，删除第 2 和第 6 个字符（"aababbab" -> "aaabbb"），
下标从 0 开始，删除第 3 和第 6 个字符（"aababbab" -> "aabbbb"）。

示例 2：


输入：s = "bbaaaaabb"
输出：2
解释：唯一的最优解是删除最前面两个字符。

 

提示：

  • 1 <= s.length <= 105
  • s[i] 要么是 'a' 要么是 'b'​ 。​

解题思路#

最容易想到的方式就是分别计算 "a" 的前缀和以及 "b" 的后缀和。然后计算两者相加最大的位置即可。

1
2
3
4
5
6
7
from itertools import accumulate

class Solution:
    def minimumDeletions(self, s: str) -> int:
        sa = accumulate(map(lambda x: int(x == "a"), s))
        sb = reversed(list(accumulate(map(lambda x: int(x == "b"), s[::-1]))))
        return len(s) - max(x + y for x, y in zip(sa, sb))

另一种方法就是找到 "a" 与 "b" 前缀和之差最大的位置。在该位置之前，删去 "b" 字符更优，在该位置之后，删去 "a" 字符更优。该位置实际上也是 "a" 的前缀和以及 "b" 的后缀和最大的位置。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def minimumDeletions(self, s: str) -> int:
        cnt = 0
        M, k = 0, 0
        for i, x in enumerate(s):
            if x == "a":
                cnt += 1
                if cnt > M:
                    M = cnt
                    k = i
            else:
                cnt -= 1

        return s.count("b", 0, k) + s.count("a", k + 1)
返回顶部

在手机上阅读