問題概要

長さ $N$ の文字列 $S$ が与えられる。文字列に対して、以下の処理を繰り返し行う。操作の結果得られる文字列の長さの最小値を求めよ。

文字列中の "fox" を削除する

制約

$1 \le N \le 2 \times 10^{5}$

考えたこと

カッコ列でよく似た問題はすごく有名。

()((()()))(())))))(((((())()(

のようなカッコ列が与えられて、"()" の部分を削除していくことで出来上がる文字列の文字数は、以下のようにして求めることができる。

空のスタックを用意して、カッコ列を左から順に次のように処理する
"(" が来たら、それをスタックの末尾に push する
")" が来たら、
- スタックの末尾が "(" ならば、それを pop する (")" も push しない)
- スタックの末尾が ")" ならば、スタックに ")" を push する

そして最後にスタックに残るものが、「最終的にできあがる文字列」ということになる。次のやつがまさにその問題。

atcoder.jp

他にも、このような考え方で解ける問題として、「カッコ列が整合しているかどうかを判定せよ」という問題がすごく有名！！！

今回の問題の場合

今回の問題も大体一緒。カッコ列の "()" が "fox" になっただけ。3 文字になっただけ。

計算量は $O(N)$ になる。

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

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