AtCoder ABC 328 D - Take ABC (茶色, 425 点)

stack を使ってカッコ列判定をする問題の亜種！

• 問題へのリンク

問題概要

3 種類の文字 'A'、'B'、'C' からなる文字列 が与えられる。この文字列に対して、「左から見ていって "ABC" があったら消す」を何度も繰り返していって残る文字列を答えよ。

制約

• 

考えたこと

かっこ列の整合性を判定する問題は有名。それを応用する感じ。カッコ列判定は 2 個の文字 "(" と ")" がセットになって消すイメージだけど、今回は 3 個の文字 "A" と "B" と "C" をセットにして消すイメージ。

計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    string S;
    cin >> S;
    
    string res = "";
    for (auto c : S) {
        if (c == 'C' && res.size() >= 2 && res.substr(res.size()-2, 2) == "AB") {                res.pop_back();
            res.pop_back();
        } else {
            res += c;
        }
    }
    cout << res << endl;
}