【C++前后缀分解】1653. 使字符串平衡的最少删除次数|1793

前后缀分解

C++前后缀分解

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

给你一个字符串 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 <= 10⁵
s[i] 要么是 ‘a’ 要么是 'b’ 。

前后缀分解

n = s.lenght
我们假定s同时存在a和b，最后一个a的下标为1，第一个b的下标为i+1。
则解为：s长度为i+1的前缀中b的数量，n-(i+1)的后缀中a的数量。
枚举s长度为i的前缀b的数量n1，长度为n-i的后缀中a的数量n2。n1+n2的最小值就是解。
全部是a或b，也符合，故无需特殊处理。i $\in$ [0,n]。
后缀的a的数等于s的转置字符串s1的前缀中a的数量。

代码

打开打包代码的方法兼述单元测试

核心代码

class Solution {public:int minimumDeletions(string s) {m_iN = s.length();auto Cnt = [&](const string& s,  char chCnt) {vector<int> ret(1);for (const auto& ch : s ) {ret.emplace_back(ret.back() + (ch == chCnt));}return ret;};auto left = Cnt(s, 'b');auto right = Cnt(string(s.rbegin(), s.rend()), 'a');int ret = INT_MAX;for (int i = 0; i <= m_iN; i++) {ret = min(ret, left[i] + right[m_iN - i]);}return ret;}int m_iN;};

单元测试

	string s ;TEST_METHOD(TestMethod1){s = "baaaa";auto res = Solution().minimumDeletions(s);AssertEx(1, res);}TEST_METHOD(TestMethod2){s = "bbbba";auto res = Solution().minimumDeletions(s);AssertEx(1, res);}TEST_METHOD(TestMethod3){s = "ab";auto res = Solution().minimumDeletions(s);AssertEx(0, res);}TEST_METHOD(TestMethod11){s = "aababbab";auto res = Solution().minimumDeletions(s);AssertEx(2, res);}TEST_METHOD(TestMethod12){s = "bbaaaaabb";auto res = Solution().minimumDeletions(s);AssertEx(2, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功