// 解答不能と判断したので, 下記, 解説を確認後, 再提出. // https://yukicoder.me/problems/no/672/editorial #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]++; } // 3. 'A' なら 1 加算, 'B' なら 1 減算(解説通り). // -> サイズ 4 * 1e6 + 1 の配列を用意し, index へ埋め込んでみる. int LIMIT = 4 * 1e6 + 1; int upper[LIMIT], lower[LIMIT]; for(int i = 0; i < LIMIT; i++) upper[i] = 0, lower[i] = LIMIT; for(int i = 0; i < len; i++){ // マイナス防止のため, 2 * 1e6 を 加算. int diff = A[i] - B[i] + (2 * 1e6); if(i > upper[diff]) upper[diff] = i; if(i < lower[diff]) lower[diff] = i; } // 4. 後処理. // ex. // BBABBAABABAAABBABAAABAAABBAAABAAABBABBBB -> 20 (OK のはず). int ans = 0; for(int i = 0; i < LIMIT; i++) ans = max(ans, upper[i] - lower[i]); cout << ans << endl; return 0; }