本文涉及的基础知识点
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 105
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);
}
扩展阅读
我想对大家说的话 |
---|
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。 |
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作 |
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注 |
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。