最長AB列 [yukicoder No.672] - はまやんはまやんはまやん

解法

Sの文字数をNとしておく。
徐々に計算量を落としながら解法に近づけていこう。

まず、区間を全探索するとO(N^2)かかり、AとBの数が等しいかのチェックにO(N)かかる。
これはO(N^3)なので、もちろんダメ。
　
チェックをO(1)でできるようにしよう。
Aを1, Bを-1として考えて累積和を取っておこう。
すると、区間の累積和を取って、それが0であれば、AとBの数が等しいと言える。
累積和は事前に構築でO(N)かかるが、取得はO(1)である。
これでO(N^2)が実現できる。
　
次に、連続区間の右端を全探索することでTLEを回避するというよくある方針を使う。
右端を固定したときに、知りたいのは、累積和を取ると0であり、そのうち最も左にある左端である。
これを累積和として考えると、[0,r]=[0,l]を満たし、最小のlが分かればいい。
これは累積和が分かった時点で、その時の右端をメモしておけばいい。
mapのmでこれを管理していく。
これでO(NlogN)

string S;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;

    int N = S.length();

    map<int, int> m;
    int p = 0;
    m[0] = -1;
    int ans = 0;

    rep(i, 0, N) {
        char c = S[i];
        if (c == 'A') p++;
        else p--;

        if (m.count(p)) chmax(ans, i - m[p]);
        if (!m.count(p)) m[p] = i;
    }
    cout << ans << endl;
}