srm551div2M.cpp

class ColorfulChocolates {
public:
  int maximumSpread(string chocolates, int maxSwaps) {
    int n = chocolates.size();
    int ms[26][n];
    int i, j, k;
    for(i = 0; i < 26; i++){
      for(j = 0; j < n; j++){
        ms[i][j] = 0;
      }
    }
    
    for(i = 0; i < 26; i++){
      for(j = 0; j < n; j++){
        int k1 = j-1;
        int k2 = j+1;
        int offset1 = j-1;
        int offset2 = j+1;
        if((chocolates[j]-'A') == i) {
          ms[i][j] = 1;
        }else{
          offset1 = offset2 = j;
        }
        int mSwap = maxSwaps;
        int non=5000;
        while(mSwap > 0){
          int cost1, cost2;
          for(; k1 >= 0 && (chocolates[k1]-'A') != i; k1--);
          for(; k2 < n && (chocolates[k2]-'A') != i; k2++);
          if(k1>=0) cost1 = (offset1-k1);
          else cost1 = non;
          if(k2 < n) cost2 = (k2-offset2);
          else cost2 = non;
          if( cost1 <= cost2 && cost1 <= mSwap){
              offset1--;
              ms[i][j]++;
              k1--;
              mSwap -= (offset1-k1);
          }else if( cost1 > cost2 && cost2 <= mSwap){
              offset2++;
              ms[i][j]++;
              k2++;
              mSwap -= (k2-offset2);
          }else {
            break;
          }
        }
      }
    }

    int res = 0;
    for(i = 0; i < 26; i++){
      for(j = 0; j< n; j++){
        res = max(res, ms[i][j]);
      }
    }
    return res;
  }
}