// 解答不能と判断したので, 下記, 解説を確認後, 再提出. // https://yukicoder.me/problems/no/672/editorial // WA版. #include using namespace std; const int LIMIT = 2 * 1e6; int main() { // 1. 入力情報取得. string S; cin >> S; // 2. 'A' なら 1 加算, 'B' なら 1 減算(解説通り). int l = S.size(); int a[l]; a[0] = (S[0] == 'A') ? l + 1 : l - 1; for(int i = 1; i < l; i++){ if(S[i] == 'A') a[i] = a[i - 1] + 1; if(S[i] == 'B') a[i] = a[i - 1] - 1; } // for(int i = 0; i < l; i++) cout << "a[" << i << "]=" << a[i] << endl; // 3. 各 a[i] の 情報 を, vector に保存. // 2 * l + 1 とする必要あり(※test1.txt の WA原因と推定). vector> vi(2 * l + 1, vector(0)); for(int i = 0; i < l; i++) vi[a[i]].push_back(i); // 4. 集計. int ans = 0; // for(int i = 0; i < l * 2 + 1; i++){ // if(!vi[i].empty()){ // cout << "i=" << i << " p="; // for(auto &p : vi[i]) cout << p << " "; // cout << endl; // } // } // ex. // BBABBAABABAAABBABAAABAAABBAAABAAABBABBBB // i=37 p=4 // i=38 p=1 3 5 7 9 // i=39 p=0 2 6 8 10 14 16 // i=40 p=11 13 15 17 // i=41 p=12 18 20 // i=42 p=19 21 25 39 // i=43 p=22 24 26 38 // i=44 p=23 27 29 37 // i=45 p=28 30 34 36 // i=46 p=31 33 35 // i=47 p=32 // -> i = 42 で, 39 - 19 = 20(OK のはず) の 最大値 を 取ってこれるはず. for(int i = 0; i < l * 2 + 1; i++){ if(!vi[i].empty()){ sort(vi[i].begin(), vi[i].end()); ans = max(ans, vi[i].back() - vi[i].front()); } } // 5. 後処理. cout << ans << endl; return 0; }