JavaScriptで有効な括弧列にするために必要な最小の追加数を求める方法

問題

今回は、'[' と ']' のみで構成される文字列 str を受け取るJavaScript関数を作成します。

この関数の目的は、結果として得られる括弧の組み合わせが有効（バランスの取れた状態）になるように、必要な最小数の角括弧（'[' または ']'）を任意の位置に追加することです。そして最後に、追加した括弧の最小数を返します。

例えば、関数への入力が以下の場合を考えてみましょう。

入力

const str = '[]]';

出力

const output = 1;

出力の説明

先頭に '[' を1つ追加すれば、文字列は [[]] となりバランスが取れます。したがって答えは 1 です。

アルゴリズムの考え方

この問題はスタックを使用せず、シンプルなカウンター方式で効率的に解くことができます。基本的な発想は以下の通りです。

1. 変数 left と right を 0 で初期化します。left は「対応する ']' をまだ見つけていない '[' の数」、right は「対応する '[' が存在せず余ってしまった ']' の数」を追跡します。
2. 文字列を先頭から順に走査し、'[' が出現したら left をインクリメントします。
3. ']' が出現した場合、left > 0 であれば未処理の '[' とマッチさせられるので left をデクリメントします。マッチできる '[' が存在しない場合は、その ']' は余りになるため right をインクリメントします。
4. 走査終了後、left + right を返せば、それが必要な追加括弧の最小数です。

このアプローチでは、各文字を一度だけ調べるため、時間計算量は O(n)、空間計算量は O(1) となります。

実装例

const findAdditions = (str = '') => {
    let left = 0;
    let right = 0;
    for (let i = 0; i < str.length; i++) {
        if (str[i] === '[') {
            left += 1;
        } else if (str[i] === ']') {
            if (left > 0) {
                left -= 1;
            } else {
                right += 1;
            }
        }
    }
    return left + right;
};
console.log(findAdditions(str));

出力

1

コードのポイント

• 単一パスで完結: 文字列を一度だけ走査するため、非常に高速です。
• 追加メモリ不要: スタックや配列を使わず、2つの整数カウンターだけで済みます。
• 正確性の保証: 余った '[' の後ろに ']' を、余った ']' の前に '[' をそれぞれ追加すれば必ず有効な文字列になるため、left + right が理論上の最小値と一致します。