fork(1) download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.     while (true){
  8.     int t;
  9.     cin >> t;
  10.     cin.ignore();
  11.     if (t==0)return 0;
  12.     string ab;
  13.     getline(cin,ab);
  14.     int a[1000]={0};
  15.     int dp[ab.size()];
  16.     dp[0]=1;
  17.     a[ab[0]]=1;
  18. int c2(0);
  19. int different(1);
  20. int character(2);
  21. int maxi(0);
  22.     for (int c(1);c<ab.size();c++,character++){
  23.             maxi=max(maxi,dp[c-1]);
  24.         if (a[ab[c]]==0){different++;}a[ab[c]]++;
  25.         if (different<=t){dp[c]=character-c2;}
  26.         else {
  27.             if (a[ab[c2]]-1==0){dp[c]=character-c2-1;a[ab[c2]]=0;c2++;different--;}
  28.             else
  29.             {
  30.  
  31.                 for (;different>t;c2++){a[ab[c2]]--;if (a[ab[c2]]==0)different--;}
  32.                 dp[c]=different;
  33.                 maxi=max(maxi,dp[c]);
  34.             }
  35.         }
  36.  
  37.  
  38.  
  39.  
  40. }
  41. cout << maxi << endl;
  42.     }
  43.     return 0;
  44. }
  45.  
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
5
This can't be solved by brute force.
1
Mississippi
0
stdout
copy 
7
2
https://ideone.com/zMzeF9
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!