思路
记录每个字母为开头的最大长度，根据这个长度更新之后的字符数量，最后全部相加。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
public:
int findSubstringInWraproundString(string p) {
vector<int> dp(26);
int subSL=1;
char startS=p[0]-'a';
for(int i=0;i+1<p.length();i++){
char c1=p[i]-'a';
char c2=p[i+1]-'a';
if((c1+1)%26==c2){
subSL++;
}else{
dp[startS]=max(dp[startS],subSL);
subSL=1;
startS=c2;
}
}
dp[startS]=max(dp[startS],subSL);
for(int i=0;i<26;i++){
if(dp[i]){
for(int k=1;k<dp[i];k++){
dp[(i+k)%26]=max(dp[(i+k)%26],dp[i]-k);
}
}
}
int res=0;
for(int i=0;i<26;i++){
res+=dp[i];
}
return res;
}
};
|
[^1]: