Cân bằng ngoặc đơn trong chuỗi JavaScript

Mô tả bài toán

Cho chuỗi chỉ chứa '(' và ')'. Chèn thêm ngoặc tối thiểu để cân bằng, trả về số lượng chèn.

Ví dụ minh họa

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));

Kết quả

2

Giải thích

Dùng mảng làm stack. Gặp '(' push, gặp ')' pop nếu top là '(', ngược lại push placeholder. Số phần tử còn lại = số ngoặc cần thêm.

Cách tối ưu O(1) space

const balanceParanthesis = str => {
  let open = 0, insert = 0;
  for (const c of str) {
    if (c === '(') open++;
    else if (open > 0) open--;
    else insert++;
  }
  return insert + open;
};