使字符串平衡的最少删除次数【LC1653】
给你一个字符串
s，它仅包含字符'a'和'b'。你可以删除
s中任意数目的字符，使得s平衡 。当不存在下标对(i,j)满足i < j，且s[i] = 'b'的同时s[j]= 'a'，此时认为s是 平衡 的。请你返回使
s平衡 的 最少 删除次数。
这两天感觉脑子有点秀逗
前后缀分解
- 思路：
- 如果字符串是平衡的，那么所有的a都在所有b的左边，此时有两种特殊情况字符串全为a或者全部b
- 那么我们可以枚举所有的分割线，将s分为前缀和后缀，并保证前缀都是a后缀都是b，那么我们需要统计前缀中b的个数和后缀中a的个数，删除的次数即为两者之和，记录最小值返回既可
- 既可
- 实现
先统计整个后缀字符串中所有的a的个数，即为整个字符串都为b时需要的删除次数d e l ，然后右移分割线，如果当前字符是a，那么删除次数减小1，如果当前字符是b，那么删除字符增加1
class Solution { public int minimumDeletions(String s) { // a全部在b的左边 int del = 0; for (char c : s.toCharArray()){ if (c == 'a'){ del++; } } int res = del; for (char c : s.toCharArray()){ if (c == 'a'){ del--; res = Math.min(del, res); }else{ del++; } // 'a' -> -1 'b' -> 1 // del += (c - 'a') * 2 - 1; } return res; } }
复杂度
- 时间复杂度：O ( n )
- 空间复杂度：O ( 1 )
动态规划
- 思路：考虑s的某个字母对结果的影响
- 如果
s[i]是b，那么不需要删除，s[0,i]为平衡字符串所需要的次数即为s[0,i-1]为平衡字符串的次数
- 字符串的次数
- 如果
s[i]是a，那么即可以保留它也可以删除它
- 保留它，那么需要删除
s[0,i-1]中所有的b
- 删除它，
s[0,i]为平衡字符串所需要的次数即为「s[0,i-1]为平衡字符串的次数」+1
- 因此可以使用动态规划实现
- 动态规划
- 确定dp数组（dp table）以及下标的含义
dp[i]为使s的前i个字母平衡的最少删除次数。
2.确定递推公式
- 如果
s[i]是b
3.dp数组如何初始化
dp[0] = 0;
4.确定遍历顺序
从前往后遍历nums
5.举例推导dp数组
class Solution { public int minimumDeletions(String s) { int n = s.length(); int[] dp = new int[n + 1]; dp[0] = 0; int cntB = 0; for (int i = 0; i < n; i++){ if (s.charAt(i) == 'b'){ dp[i + 1] = dp[i]; cntB++; }else{ dp[i + 1] = Math.min(dp[i] + 1, cntB); } } return dp[n]; } }
复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(n)
优化空间复杂度
class Solution { public int minimumDeletions(String s) { int n = s.length(); int dp = 0; int cntB = 0; for (int i = 0; i < n; i++){ if (s.charAt(i) == 'b'){ cntB++; }else{ dp = Math.min(dp + 1, cntB); } } return dp; } }
复杂度
时间复杂度：O ( n )
空间复杂度：O ( 1 )
