跳到主要内容

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

· 阅读需 3 分钟

1、题干​

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

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

请你返回使 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'​ 。​

本题跟剑指 Offer II 092. 翻转字符的思路一样

2、思路1​

循环剔除所有 ba 子串并累加剔除次数

3、代码​

function minimumDeletions(s: string): number {
    let ans = 0;
    while (s.includes('ba')) s = s.replace(/ba/g, () => (ans++, ''));
    return ans;
};

4、执行结果​

image.png

5、思路2​

思路1实际上是消除所有字符 b 后面的字符 a，可以使用常规遍历模拟消除过程。

具体实现时需要遍历字符串 s 两次，先统计字符 a 的个数，再消除字符 a。

6、代码​

function minimumDeletions(s: string): number {
    let ac = 0;
    for (let i = 0; i < s.length; i++) {
        if (s[i] === 'a') ac++;
    };

    let ans = 0, bc = 0;
    for (let i = 0; ac > 0 && i < s.length; i++) {
        if (s[i] === 'a') bc > 0 ? bc-- : ac--;
        else ans++, bc++, ac--;
    }

    return ans;
};

7、复杂度​

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(1)O(1)

8、执行结果​

image.png