หาความยาววงเล็บคู่ที่ถูกต้องและยาวที่สุดใน JavaScript

กำหนดสตริงที่มีเพียงตัวอักษร '(' และ ')' เราต้องหาความยาวของซับสตริงวงเล็บคู่ที่ถูกต้อง (well-formed) ที่ยาวที่สุด

ชุดวงเล็บคู่ถือว่าถูกต้อง (well-formed) ก็ต่อเมื่อสำหรับวงเล็บเปิดทุกตัว มีวงเล็บปิดที่สอดคล้องกัน

เช่น:

'(())()' เป็นวงเล็บคู่ที่ถูกต้อง
'())' ไม่ใช่วงเล็บคู่ที่ถูกต้อง
'()()()' เป็นวงเล็บคู่ที่ถูกต้อง

ตัวอย่าง

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