カッコ列系の問題!
問題概要
長さ の文字列 が与えられる。文字列に対して、以下の処理を繰り返し行う。操作の結果得られる文字列の長さの最小値を求めよ。
- 文字列中の "fox" を削除する
制約
考えたこと
カッコ列でよく似た問題はすごく有名。
()((()()))(())))))(((((())()(
のようなカッコ列が与えられて、"()" の部分を削除していくことで出来上がる文字列の文字数は、以下のようにして求めることができる。
- 空のスタックを用意して、カッコ列を左から順に次のように処理する
- "(" が来たら、それをスタックの末尾に push する
- ")" が来たら、
- スタックの末尾が "(" ならば、それを pop する (")" も push しない)
- スタックの末尾が ")" ならば、スタックに ")" を push する
そして最後にスタックに残るものが、「最終的にできあがる文字列」ということになる。次のやつがまさにその問題。
他にも、このような考え方で解ける問題として、「カッコ列が整合しているかどうかを判定せよ」という問題がすごく有名!!!
今回の問題の場合
今回の問題も大体一緒。カッコ列の "()" が "fox" になっただけ。3 文字になっただけ。
計算量は になる。
#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; }