-
-
Notifications
You must be signed in to change notification settings - Fork 299
/
1156.cpp
30 lines (28 loc) · 988 Bytes
/
1156.cpp
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
__________________________________________________________________________________________________
class Solution {
public:
int maxRepOpt1(string text) {
int n=text.size(),i,j,k,ans=0,s,a[20005],t[20005];
char c;
a[0]=0;
for(c='a';c<='z';c++)
{
a[0]=0;
for(i=0;i<n;i++)a[i+1]=text[i]==c;
for(i=1;i<=n;i++)a[i]+=a[i-1];
if(!a[n])continue;
for(i=0;i<=n;i++)a[i]+=n-i;
fill(t+1,t+n+2,n+1);
for(i=s=0;i<=n;i++)
{
for(j=a[i]+1,k=i;j;j^=j&-j)k=min(k,t[j]);
s=max(s,i-k);
for(j=a[i];j<=n+1;j+=j&-j)t[j]=min(t[j],i);
}
ans=max(ans,min(s,a[n]));
}
return ans;
}
};
__________________________________________________________________________________________________
__________________________________________________________________________________________________