黑龙江省住房与建设厅网站,wordpress 底部代码,wordpress有声电台,微信社群营销文章目录1. 题目2. 解题1. 题目
给定一个字符串#xff0c;我们想知道满足以下两个条件的子串最多出现了多少次#xff1a;
子串的长度在之间 [minLength, maxLength] 子串的字符种类不超过 maxUnique 写一个函数 getMaxOccurrences #xff0c;其返回满足条件的子串最多出…
文章目录1. 题目2. 解题1. 题目
给定一个字符串我们想知道满足以下两个条件的子串最多出现了多少次
子串的长度在之间 [minLength, maxLength] 子串的字符种类不超过 maxUnique 写一个函数 getMaxOccurrences 其返回满足条件的子串最多出现次数。
输入:
s abcde
minLength 2
maxLength 5
maxUnique 3
输出: 1
说明符合条件的子串有 ab, bc, cd, de, abc, bcd, cde 。
每一个子串只出现了一次因此答案是 1。https://tianchi.aliyun.com/oj/231203672248052266/245580596369363584
2. 解题
class Solution {
public:/*** param s: string s* param minLength: min length for the substring* param maxLength: max length for the substring* param maxUnique: max unique letter allowed in the substring* return: the max occurrences of substring*/int maxcount 0;vectorlong long pow;int getMaxOccurrences(string s, int minLength, int maxLength, int maxUnique) {// write your code herepow.resize(27);pow[0] 1;for(int i 1; i 26; i) {pow[i] pow[i-1]*26;//预处理 26 的幂次方}for(int len minLength; len maxLength; len) { // 暴力枚举子串长度help(s, len, maxUnique);}return maxcount;}void help(string s, int len, int maxUnique) {unordered_maplong long, int count;//字符串哈希值字符串个数unordered_mapchar, int m;//滑窗内的字符计数int i 0;long long hash 0;for( ; i len-1; i){m[s[i]];hash hash*26s[i]-a;}for(int j 0 ; i s.size(); i){m[s[i]];hash hash*26s[i]-a;if(m.size() maxUnique i-j1 len){ // 窗口内子串字符种类满足长度达到 lenif(count[hash] maxcount)maxcount count[hash];}while(i-j1 len || m.size() maxUnique){ // 长度超了或者 字符种类超了hash - pow[i-j]*(s[j]-a);//最前面的字符哈希值减去if(--m[s[j]] 0)//计数 -1m.erase(s[j]);j;}}}
};12ms C
同题LeetCode 1297. 子串的最大出现次数 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
