#include using namespace std; const int LIMIT = 2 * 1e6; int main() { // 1. 入力情報取得. string S; cin >> S; // 2. 'A', 'B' の 出現数 の 累積和は? int len = S.size(); int A[len], B[len]; for(int i = 0; i < len; i++) A[i] = 0, B[i] = 0; if(S[0] == 'A') A[0]++; if(S[0] == 'B') B[0]++; for(int i = 1; i < len; i++){ A[i] = A[i - 1], B[i] = B[i - 1]; if(S[i] == 'A') A[i]++; if(S[i] == 'B') B[i]++; } // ex. // BBAAABAAABBAB // 'A' の 累積出現数 -> 0 0 1 2 3 3 4 5 6 6 6 7 7 // 'B' の 累積出現数 -> 1 2 2 2 2 3 3 3 3 4 5 5 6 // for(int i = 0; i < len; i++) cout << A[i] << " "; // for(int i = 0; i < len; i++) cout << B[i] << " "; // 3. 文字列S の i番目までの最長AB列を順次求めていく. // -> これを, dp[i] と置いてみる. int dp[len]; for(int i = 0; i < len; i++) dp[i] = 0; // 各文字(S[i])から探索開始した時に, 'A', 'B' の 出現数 が等しくなる場所を, 2分探索. for(int i = 0; i < len; i++){ // 左: l番目, 右: r番目. int l = i, r = len - 1; while(l < r){ // 'A', 'B' の 出現数 を 比較. int a = A[r] - A[l], b = B[r] - B[l]; // cout << "a=" << a << " r=" << r << " b=" << b << " l=" << l << endl; // 同じ場合は, 終了. if(a == b) break; // 'A', 'B' の 出現数 に差がある場合は, 中心を移動. if(a > b && A[r] >= B[r]) r = (l + r - 1) / 2; if(a > b && A[r] < B[r]) l = (l + r + 1) / 2; if(a < b && A[r] >= B[r]) l = (l + r + 1) / 2; if(a < b && A[r] < B[r]) r = (l + r - 1) / 2; } dp[i] += A[r] - A[l]; dp[i] += B[r] - B[l]; } // ex. // BBABBAABABAAABBABAAABAAABBAAABAAABBABBBB // S[i]スタートの最長AB列の長さ // -> 4 4 4 0 0 0 0 0 0 0 0 6 6 2 0 2 0 0 0 20 0 18 0 0 0 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 // for(int i = 0; i < len; i++) cout << dp[i] << " "; // 4. 後処理. int ans = 0; for(int i = 0; i < len; i++) ans = max(ans, dp[i]); cout << ans << endl; return 0; }