本文涉及的基础知识点
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
题目
给你一个字符串 s 和一个正整数 k 。
用 vowels 和 consonants 分别表示字符串中元音字母和辅音字母的数量。
如果某个字符串满足以下条件，则称其为 美丽字符串 ：
vowels == consonants，即元音字母和辅音字母的数量相等。
(vowels * consonants) % k == 0，即元音字母和辅音字母的数量的乘积能被 k 整除。
返回字符串 s 中 非空美丽子字符串 的数量。
子字符串是字符串中的一个连续字符序列。
英语中的 元音字母 为 ‘a’、‘e’、‘i’、‘o’ 和 ‘u’ 。
英语中的 辅音字母 为除了元音字母之外的所有字母。
示例 1：
输入：s = “baeyh”, k = 2
输出：2
解释：字符串 s 中有 2 个美丽子字符串。
- 子字符串 “baeyh”，vowels = 2（[“a”,“e”]），consonants = 2（[“y”,“h”]）。
可以看出字符串 “aeyh” 是美丽字符串，因为 vowels == consonants 且 vowels * consonants % k == 0 。 - 子字符串 “baeyh”，vowels = 2（[“a”,“e”]），consonants = 2（[“b”,“y”]）。
可以看出字符串 “baey” 是美丽字符串，因为 vowels == consonants 且 vowels * consonants % k == 0 。
可以证明字符串 s 中只有 2 个美丽子字符串。
示例 2：
输入：s = “abba”, k = 1
输出：3
解释：字符串 s 中有 3 个美丽子字符串。 - 子字符串 “abba”，vowels = 1（[“a”]），consonants = 1（[“b”]）。
- 子字符串 “abba”，vowels = 1（[“a”]），consonants = 1（[“b”]）。
- 子字符串 “abba”，vowels = 2（[“a”,“a”]），consonants = 2（[“b”,“b”]）。
可以证明字符串 s 中只有 3 个美丽子字符串。
示例 3：
输入：s = “bcdf”, k = 1
输出：0
解释：字符串 s 中没有美丽子字符串。
参数范围：
1 <= s.length <= 5 * 104
1 <= k <= 1000
s 仅由小写英文字母组成。
方法一
分析
时间复杂度
O(n)
大致步骤
记录前缀和后，枚举左右端点。
| setVowel | 所有元音字符 |
| vPre1[i] | 前i个字符中元音的数量 |
| vPre2[i] | 前i个字符中辅音的数量 |
代码
核心代码
class Solution { public: int beautifulSubstrings(string s, int k) { m_c = s.length(); std::unordered_set setVowel = { ‘a’,‘e’,‘i’,‘o’ , ‘u’ }; vector vPre1 = { 0 }, vPre2 = { 0 }; for (const char& ch : s) { if (setVowel.count(ch)) { vPre1.emplace_back(vPre1.back() + 1); vPre2.emplace_back(vPre2.back() ); } else { vPre1.emplace_back(vPre1.back() ); vPre2.emplace_back(vPre2.back() + 1); } } int iRet = 0; for(int i = 0 ; i < m_c ; i++ ) for (int j = i; j < m_c; j++) { const int iNum1 = vPre1[j + 1] - vPre1[i]; const int iNum2 = vPre2[j + 1] - vPre2[i]; if (iNum1 != iNum2) { continue; } if (0 != iNum1 * iNum2% k ) { continue; } iRet++; } return iRet; } int m_c; };
测试用例
template void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { string s; int k,res; { Solution slu; s = “baeyh”; k = 2; res = slu.beautifulSubstrings(s, k); Assert(res, 2); } { Solution slu; s = “abba”; k = 1; res = slu.beautifulSubstrings(s, k); Assert(res, 3); } { Solution slu; s = “bcdf”; k = 1; res = slu.beautifulSubstrings(s, k); Assert(res, 0); } { Solution slu; s = “ihroyeeb”; k = 5; res = slu.beautifulSubstrings(s, k); Assert(res, 0); } }
方案二
s[left,right]是美丽字符的条件。
一，元音辅音相等。我们记录所有sub[left] = vPre1[left]-vPre2[left]，即元音辅音之差。如果sub[left]等于sub[right]，则元音辅音相等。
二，数量的平方是k的倍数。我可以转成等效问题：数量必须是m的倍数。如：k=4,则m=2。k=3，则m=3。k=12，m=6。显然：m小于等于k，且m不会为0。对于每个left，我们无需记录它的元音数量，只需要记录它的元音数量%m。
时间复杂度
如果用有序映射记录状态的数量，则时间复杂度为：O(nlognm)。
枚举每个每个美丽字符串的右端点时间复杂度O(n)，查询合法的对应left数量O(lognm)。如果用哈希映射记录状态和数量，总时间复杂度降到O(n)。
代码
class Solution { public: int beautifulSubstrings(string s, int k) { m_c = s.length(); std::unordered_set<char> setVowel = { 'a','e','i','o' , 'u' }; vector<int> vPre1 = { 0 }, vPre2 = { 0 }; for (const char& ch : s) { if (setVowel.count(ch)) { vPre1.emplace_back(vPre1.back() + 1); vPre2.emplace_back(vPre2.back()); } else { vPre1.emplace_back(vPre1.back()); vPre2.emplace_back(vPre2.back() + 1); } } int m = 0; for (m = 1; 0 != m * m % k; m++); int iRet = 0; std::unordered_map<int, std::unordered_map<int,int>> mSub; for (int i = 0; i < m_c; i++) { const int iSub = vPre1[i+1] - vPre2[i+1]; const int iNeed = vPre1[i + 1] % m; if (mSub.count(iSub)) { if(mSub[iSub].count(iNeed)) { iRet += mSub[iSub][iNeed]; } } { const int iSub = vPre1[i] - vPre2[i]; mSub[iSub][vPre1[i]%m]++; } } return iRet; } int m_c; };
优化代码
分析
优化点：
一，无需前缀和，记录当前元音数量就可以了。当前辅音数量=当前字符总数量-当前元音数量。
二，用std::pair<int,int> 做key。
代码
class Solution { public: int beautifulSubstrings(string s, int k) { m_c = s.length(); std::unordered_set<char> setVowel = { 'a','e','i','o' , 'u' }; int m = 0; for (m = 1; 0 != m * m % k; m++); int iRet = 0; int iVowelNum = 0; std::map<std::pair<int, int>, int> mSubVowelToNum; for (int i = 0; i < m_c; i++) { const int preVowel = iVowelNum; if (setVowel.count(s[i])) { iVowelNum++; } const int iSub = iVowelNum - (i+1- iVowelNum);//当前元音数量减辅音数量 auto pr = std::make_pair(iSub, iVowelNum%m); if (mSubVowelToNum.count(pr)) { iRet += mSubVowelToNum[pr]; } { const int iSub = preVowel - (i - preVowel); auto pr = std::make_pair(iSub, preVowel%m); mSubVowelToNum[pr]++; } } return iRet; } int m_c; };
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
