题目描述
给你一个仅由小写英文字母组成的字符串 s 。
如果一个字符串仅由单一字符组成,那么它被称为 特殊 字符串。例如,字符串 "abc" 不是特殊字符串,而字符串 "ddd"、"zz" 和 "f" 是特殊字符串。
返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度,如果不存在出现至少三次的特殊子字符串,则返回 -1 。
子字符串 是字符串中的一个连续 非空 字符序列。
思路
- 统计每个字母出现时的下标,用vector<vector<int>> cnt(26)记录字母和其对应的下标,cnt[i]为字母,vector<int> idx = cnt[i],idx为该字母下标的集合
- 遍历cnt中所有字母,找到每个字母出现 至少三次 的 最长特殊子字符串
- 如果cnt[i].size() < 3,说明该字母出现的次数小于3次,不可能有 至少三次 的最长特殊子字符串,略过
- 遍历cnt时,先找到cnt[i]的最长特殊字符串length,也就是连续的cnt[i]的长度。接着遍历idx,统计length出现的次数,如果过次数 < 3,length--,重复遍历idx,直到找到 出现至少三次的最长特殊子字符串或者length = 1
- 比较每一个字母的length,找到最大的
代码
class Solution {
public:
int maximumLength(string s) {
int n = s.size();
vector<vector<int>> cnt(26);
for(int i = 0;i < n;i++){
cnt[s[i] - 'a'].push_back(i);
}
int maxLength = -1;
for(int i = 0;i < 26;i++){
if(cnt[i].size() < 3) continue;
vector<int> idx = cnt[i];
int m = idx.size();
int start = 0,end = 0;
int length = 0;
while(end < m){
if(idx[end] - idx[start] == end - start) end++;
else{
length = max(length,end - start);
start = end;
}
}
length = max(length,end - start);
int count = 0;
while(length > 1){
for(int j = 0;j < m;j++){
int k = j + length - 1;
if(k < m && idx[j] - idx[k] == j - k) count++;
}
if(count >= 3) break;
count = 0;
length--;
}
maxLength = max(maxLength,length);
}
return maxLength;
}
};
标签:找出,end,idx,int,2981,cnt,length,字符串
From: https://www.cnblogs.com/EavenWang/p/18221199