C++で文字列のバランスを取るための最小ブラケット挿入数を求める

「(」と「)」のみで構成される文字列 s が与えられたとき、この文字列をバランスの取れた状態にするために挿入が必要な括弧の最小数を求める問題について解説します。

例えば、入力が「(()))(」の場合、出力は 2 になります。これは「(()))(」を「((()))()」のように変形することで、バランスの取れた文字列にできるからです。

アルゴリズムの考え方

この問題は、以下の手順で解くことができます。

• カウンタとして o := 0、cnt := 0 を初期化します。
• i := 0 から文字列 s の長さ未満の間、i を 1 ずつ増やしながら以下を繰り返します。
  • s[i] が「(」と等しい場合:o を 1 増やします（開き括弧の余りを記録）。
  • それ以外の場合:
    • o が 0 以外であれば、o を 1 減らします（対応する開き括弧が存在するため）。
    • o が 0 の場合は、cnt を 1 増やします（対応する開き括弧がない閉じ括弧なので、追加が必要）。
• 最後に cnt + o を返します。cnt は余分な閉じ括弧の数、o は対応する閉じ括弧を持たない開き括弧の数です。

C++による実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int solve(string s) {
        int o = 0;
        int cnt = 0;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == '('){
                o++;
            } else {
                if(o)
                    o--;
                else
                    cnt++;
            }
        }
        return cnt + o;
    }
};
int main(){
    Solution ob;
    cout << (ob.solve("(()))("));
}

入力

"(()))("

出力

2

計算量について

このアルゴリズムは文字列を一度だけ走査するため、時間計算量は O(n)、空間計算量は O(1) となります。ここで n は文字列の長さです。スタックなどの追加データ構造を使わずに、2つの整数カウンタだけで効率的に解ける点がこの手法の魅力です。