使字符串平衡的最少删除次数
难度:
标签:
题目描述
代码结果
运行时间: 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,这样的处理逻辑是基于什么考虑?
▷🦆
在算法实现中,如果字符串s全部由'b'组成,b_cnt的处理会如何影响最终的删除次数计算?
▷🦆
题解中提到的删除字符操作是如何确保最终字符串的平衡性的?是否有可能存在未被考虑到的边缘情况?
▷🦆
题解中的贪心策略是否适用于字符串中'a'和'b'极度不平衡的情况?例如,字符串几乎全是'a'只有一个'b',这时的处理逻辑是否依然有效?
▷