【JavaScript】スタックで最長の有効な括弧部分文字列の長さを求める方法

'(' と ')' の2種類の文字だけで構成された文字列が与えられたとき、その中に含まれる最長の有効な（正しく対応した）括弧部分文字列の長さを求める方法を、JavaScriptで解説します。

整形式の括弧列とは？

括弧の並びが「整形式（well-formed）」であるためには、すべての開き括弧に対して、それに対応する閉じ括弧が存在しなければなりません。具体例で確認してみましょう。

'(())()' は整形式の括弧列
'())' は整形式ではない
'()()()' は整形式の括弧列

解き方：スタックを活用する

この問題はスタック（Stack）を使うことで効率的に解けます。手順は以下のとおりです。

1. 文字列を1文字ずつ走査し、スタックには各文字のインデックスを保存します。
2. 開き括弧 '(' を見つけたら、そのインデックスをスタックにプッシュします。
3. 閉じ括弧 ')' を見つけた場合、スタックの先頭が対応する開き括弧のインデックスであればポップします。対応できない場合（スタックが空、または先頭が閉じ括弧のインデックス）は、そのインデックスを区切り位置としてプッシュします。
4. 走査が終わったら、スタックの末尾に文字列長、先頭に -1 を番兵として追加し、隣接する要素の差分から最大値を計算します。これが答えとなります。

実装例

const str = '(())()((('; 
 const longestValidParentheses = (str = '') => { 
 var ts = str.split(''); 
 var stack = [], max = 0; 
 ts.forEach((el, ind) => { 
 if (el == '(') { 
 stack.push(ind); 
 } 
 else { 
 if (stack.length === 0 || ts[stack[stack.length - 1]] == ')'){ 
 stack.push(ind); 
 } 
 else { 
 stack.pop(); 
 }; 
 } 
 }); 
 stack.push(ts.length); 
 stack.splice(0, 0, -1); 
 for (let ind = 0; 
 ind< stack.length - 1; ind++) { 
 let v = stack[ind+1] - stack[ind] - 1; max = Math.max(max, v); 
 }; 
 return max; 
 }; console.log(longestValidParentheses(str));

出力結果

このコードをコンソールで実行すると、次のような出力が得られます。

6

入力文字列 '(())()(((' の場合、先頭の '(())()' が最も長い整形式の括弧部分文字列となり、その長さは 6 文字です。