当前位置：首页 > news >正文

【C++前缀和状态压缩】1371. 每个元音包含偶数次的最长子字符串|2040

news 2025/5/18 17:22:55

本文涉及的基础知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频

位运算、状态压缩、枚举子集汇总

LeetCode1371. 每个元音包含偶数次的最长子字符串

给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 ‘a’，‘e’，‘i’，‘o’，‘u’ ，在子字符串中都恰好出现了偶数次。
示例 1：
输入：s = “eleetminicoworoep”
输出：13
解释：最长子字符串是 “leetminicowor” ，它包含 e，i，o 各 2 个，以及 0 个 a，u 。
示例 2：
输入：s = “leetcodeisgreat”
输出：5
解释：最长子字符串是 “leetc” ，其中包含 2 个 e 。
示例 3：
输入：s = “bcbcbc”
输出：6
解释：这个示例中，字符串 “bcbcbc” 本身就是最长的，因为所有的元音 a，e，i，o，u 都出现了 0 次。
提示：
1 <= s.length <= 5 x 10⁵
s 只包含小写英文字母。

前缀和

枚举nums[i…j]
令 x = preSum[i]。 x&(1<<0) 表示前i个元素中a的数量是否是奇数；x&(1<<1)表示前i个数中b的数量是否是奇数 $\cdots$ 。
用异或求前缀和。
令x1 = preSum[j+1], 如果preSum[i]也等于x1，则nums[i…j]是否合法子字符串。如果有多个符合条件的i，取最小的i，这样才能最长。
mValueIndex的key：preSum[i]；value:i。

代码

核心代码

class Solution {public:int findTheLongestSubstring(string s) {unordered_map<char, int> mCharMask;mCharMask['a'] = 1;mCharMask['o'] = 2;mCharMask['e'] = 4;mCharMask['i'] = 8;mCharMask['u'] = 16;vector<int> preSum(1);for (const auto& ch: s) {preSum.emplace_back(mCharMask[ch] ^ preSum.back());}int ret = 0;unordered_map<int, int> mValueIndex;for (int j = 0; j < s.length(); j++) {mValueIndex.emplace(preSum[j], j);if (mValueIndex.count(preSum[j + 1])) {ret = max(ret, j + 1 - mValueIndex[preSum[j + 1]]);}}return ret;}};

单元测试

	string s;TEST_METHOD(TestMethod11){s = "eleetminicoworoep";auto res = Solution().findTheLongestSubstring(s);AssertEx(13, res);}TEST_METHOD(TestMethod12){s = "leetcodeisgreat";auto res = Solution().findTheLongestSubstring(s);AssertEx(5, res);}TEST_METHOD(TestMethod13){s = "bcbcbc";auto res = Solution().findTheLongestSubstring(s);AssertEx(6, res);}

扩展阅读

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