前后缀分解

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);
		}