leetcode
leetcode 1451 ~ 1500
使字符串平衡的最少删除次数

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

难度:

标签:

题目描述

代码结果

运行时间: 164 ms, 内存: 16.5 MB


/*
 * 思路:
 * 使用 Java Stream API 实现上述逻辑。
 * 1. 计算每个位置左边的 'b' 的数量和右边的 'a' 的数量。
 * 2. 使用 IntStream 来计算每个位置删除的最小次数。
 * 3. 返回最小删除次数。
 */
import java.util.stream.IntStream;

public class Solution {
    public int minimumDeletions(String s) {
        int n = s.length();
        int[] leftB = new int[n + 1];
        int[] rightA = new int[n + 1];

        // 计算每个位置左边的 'b' 的数量
        IntStream.range(0, n).forEach(i -> leftB[i + 1] = leftB[i] + (s.charAt(i) == 'b' ? 1 : 0));

        // 计算每个位置右边的 'a' 的数量
        IntStream.range(0, n).map(i -> n - 1 - i).forEach(i -> rightA[i] = rightA[i + 1] + (s.charAt(i) == 'a' ? 1 : 0));

        // 计算最小删除次数
        return IntStream.rangeClosed(0, n).map(i -> leftB[i] + rightA[i]).min().orElse(Integer.MAX_VALUE);
    }
}

解释

方法:

该题解采用了一种贪心算法的思路。我们通过遍历字符串 s,计算在每个位置上保留字符 'a' 和 'b' 的最优数量。变量 a_cnt 用来记录保留的 'a' 的数量,而 b_cnt 用来记录保留的 'b' 的数量。遍历字符串时,每遇到一个 'a',如果之前有 'b' 出现(即 b_cnt > 0),则意味着为了保持字符串平衡,我们可以选择删除这个 'b' 而不是当前的 'a',因此 b_cnt 减一;如果没有 'b' 或者已经处理完所有 'b',则增加 a_cnt。每遇到一个 'b',直接增加 b_cnt。最后,字符串 s 的长度减去我们决定保留的 a_cnt 和 b_cnt 就是需要删除的最小字符数。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在遇到字符'a'时选择减少b_cnt而不是直接增加a_cnt,这样的处理逻辑是基于什么考虑?
这种处理逻辑基于贪心算法的思维,旨在最小化删除操作的数量来达到平衡。当我们遇到一个'a'且之前已经有累积的'b'(b_cnt > 0)时,为了使得字符串更接近平衡(即'a'和'b'的数量相等),选择删除一个先前计数的'b',而非简单地增加'a'的数量。这样做可以有效减少需要调整的后续操作,因为我们通过减少一个已存在的不平衡(多余的'b'),而不是增加新的不平衡(过多的'a')。
🦆
在算法实现中,如果字符串s全部由'b'组成,b_cnt的处理会如何影响最终的删除次数计算?
如果字符串s全部由'b'组成,这意味着在遍历字符串过程中没有遇到任何'a',因此b_cnt将等于字符串s的长度(因为每遇到一个'b',b_cnt就增加1)。由于没有'a'来触发删除'b'的操作,最终的删除次数将是0,因为所有的'b'都被保留了。这种情况下,字符串虽然不平衡(只有'b'没有'a'),但根据题解的逻辑,没有执行任何删除操作,因此删除次数为0。
🦆
题解中提到的删除字符操作是如何确保最终字符串的平衡性的?是否有可能存在未被考虑到的边缘情况?
题解中的删除字符操作主要通过减少出现次数较多的字符(在遇到另一字符时)来尽量减少总体的不平衡。这种策略通常能确保字符串尽可能接近平衡,但不保证完全平衡。例如,如果一个字符从未出现,则另一个字符永远不会被删除,结果是一个单一字符的字符串。此外,如果'a'和'b'的数量极为接近,每次删除都可能导致必须更多地依赖于字符串的初始顺序和配置,这可能会导致一些边缘案例在平衡性上不是最优的。
🦆
题解中的贪心策略是否适用于字符串中'a'和'b'极度不平衡的情况?例如,字符串几乎全是'a'只有一个'b',这时的处理逻辑是否依然有效?
题解中的贪心策略在大多数情况下是有效的,包括当一个字符的数量显著多于另一个字符时。在极端情况下,如字符串几乎全是'a'只有一个'b',这个策略仍然有效,因为它会计算出只需删除一个'b',即可使字符串尽可能接近平衡。这种情况下,尽管字符串的平衡性并不完美(因为几乎全是'a'),但考虑到删除数量最少的目标,这种处理方式仍然是合理的。

相关问题