mihaimarcel21

Longest_subsequences_after_k_muves

Nov 29th, 2020
898
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. string A;
  5. int k, n;
  6. int power(int x, unsigned int y)
  7. {
  8.     int res = 1;
  9.     while (y > 0)
  10.     {
  11.         if (y & 1)
  12.             res = res * x;
  13.  
  14.         y = y >> 1;
  15.         x = x * x;
  16.     }
  17.     return res;
  18. }
  19. int findLen(string& A, int n, int k, char ch)
  20. {
  21.     int maxlen = 1;
  22.     int cnt = 0;
  23.     int l = 0, r = 0;
  24.     while(r < n)
  25.     {
  26.         if(A[r] != ch)
  27.             ++cnt;
  28.         while(cnt > k)
  29.         {
  30.             if(A[l] != ch)
  31.                 --cnt;
  32.             ++l;
  33.         }
  34.         maxlen = max(maxlen, r - l + 1);
  35.         ++r;
  36.     }
  37.     return maxlen;
  38. }
  39. int answer(string& A, int n, int k)
  40. {
  41.     int maxlen = 1;
  42.     for(int i = 0; i < 26; ++i)
  43.         maxlen = max(maxlen, findLen(A, n, k, i+'a'));
  44.     return maxlen;
  45. }
  46. int main()
  47. {
  48.     getline(cin,A);
  49.     cin>>k;
  50.     n=A.size();
  51.     cout<<answer(A,n,k);
  52.     return 0;
  53. }
  54.  
RAW Paste Data