JavaScriptで括弧のバランスを取るための最小挿入回数を求める方法

問題の概要

「(」と「)」の2種類の文字のみで構成された文字列が与えられます。この文字列の括弧のバランスを取るために、「(」または「)」を必要な回数だけ挿入する関数を作成します。関数は、バランスを取るために挿入した文字数の最小値を返す必要があります。

例えば、次の文字列が与えられた場合を考えてみましょう。

const str = '()))';

この場合、出力は 2 になります。先頭に「((」を追加すれば「((()))」となり、括弧のバランスが取れるためです。

アルゴリズムの考え方

この問題はスタックを使うことで効率的に解けます。基本的な流れは以下の通りです。

1. 空の配列（スタック）を用意します。
2. 文字列を先頭から1文字ずつ走査します。
3. 「(」が見つかったらスタックにプッシュします。
4. 「)」が見つかった場合、スタックの先頭が「(」であればポップしてペアを消去します。そうでなければ、対応する「(」が存在しないため、挿入が必要な記号としてスタックにプッシュします。
5. 最終的にスタックに残った要素数が、挿入が必要な最小回数となります。

コード例

実際のコードは以下の通りです。

const str = '()))';
const balanceParanthesis = str => {
    let paren = [];
    for (let i = 0; i < str.length; i++) {
        if (str[i] === "(") {
            paren.push(str[i]);
        } else if (str[i] === ")") {
            if (paren[paren.length - 1] === "("){
                paren.pop();
            }else {
                paren.push("#");
            };
        };
    }
    return paren.length;
}
console.log(balanceParanthesis(str));

実行結果

コンソールには次のように出力されます。

2

コードの解説

この関数では、マッチした「(」と「)」のペアをスタックから順に取り除き、最後に残った要素の数を数えています。スタックに残る要素は次の2種類です。

• 対応する「)」が見つからなかった「(」の数
• 対応する「(」が存在しなかった「)」の数（「#」として記録）

それぞれの余分な括弧は1文字の挿入でバランスを取れるため、スタックに残った要素数がそのまま最小挿入回数となります。計算量は文字列の長さを n とすると O(n) で、非常に効率的な解法です。