#include<bits/stdc++.h>
using namespace std;
#define task "differ"
#define ii pair<int,int>
#define fi first
#define se second
// #define int long long
#define ld double
#define mp make_pair
#define lg2 20
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define fii fi.fi
#define fis fi.se
#define sfi se.fi
#define see se.se
int dx[]={0LL,0LL,1,-1,1,1,-1,-1};
int dy[]={1,-1,0LL,0LL,1,-1,1,-1};
const int maxn=2e6+5;
const int mod=1e9+7;
const int inf = 0x3f3f3f3f;
int n,s1[maxn][26],pre[maxn],tr[maxn],minn[maxn];
int b[maxn];
string s;
vector<int>a[maxn];
void sub1(){
for(int i=1;i<=n;i++){
for(int j=0;j<26;j++)
s1[i][j]=s1[i-1][j];
s1[i][s[i]-'a']++;
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
int maxx=0,minn=1e9;
for(int k=0;k<26;k++){
if(s1[j][k]-s1[i-1][k]==0)break;
maxx=max(maxx,s1[j][k]-s1[i-1][k]);
minn=min(minn,s1[j][k]-s1[i-1][k]);
}
ans=max(ans,maxx-minn);
}
}
cout<<ans;
}
void sub23(){
for(int i=1;i<=n;i++){
a[s[i]-'a'].push_back(i);
}
int ans=0;
for(int i=0;i<26;i++){
for(int j=0;j<26;j++){
int n=a[i].size(),n1=a[j].size();
if(n>0&&n1>0&&i!=j){
int l=0,r=0,m=0;
while(l<n&&r<n1){
if(a[i][l]<a[j][r]){
m++;
b[m]=1;
l++;
}
else{
m++;
b[m]=-1;
r++;
}
}
while(l<n){
m++;
b[m]=1;
l++;
}
while(r<n1){
m++;
b[m]=-1;
r++;
}
/* for(int k=1;k<=m;k++)
cout<<b[k]<<" ";
cout<<'\n';*/
tr[0]=-1;
for(int k=1;k<=m;k++){
if(b[k]==-1)
tr[k]=k-1;
else
tr[k]=tr[k-1];
}
int sum=0;
minn[0] = 0;
for(int k=1;k<=m;k++){
sum+=b[k];
if(b[k]==-1)
ans=max(ans,sum-minn[k-1]);
else{
if(tr[k]!=-1)
ans=max(ans,sum-minn[tr[k]]);
}
minn[k]=min(minn[k-1],sum);
}
}
}
}
cout<<ans;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
if(fopen(task".inp","r")){
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);}
cin>>n>>s;
s=' '+s;
sub23();
}
Compilation message
roz.cpp: In function 'int main()':
roz.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
109 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
roz.cpp:110:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
110 | freopen(task".out","w",stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
47196 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
47196 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
47192 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
47452 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
24 ms |
47444 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
85 ms |
48216 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
657 ms |
56228 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
633 ms |
55836 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
619 ms |
55992 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
625 ms |
56356 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
