Cho một chuỗi chỉ chứa các ký tự '(' và ')', chúng tôi tìm độ dài của chuỗi con trong dấu ngoặc đơn hợp lệ (được tạo hình tốt) dài nhất.
Một tập hợp các dấu ngoặc đơn đủ điều kiện để trở thành một cặp ngoặc đơn đúng cách, nếu và chỉ khi, đối với mỗi dấu ngoặc đơn mở, nó chứa một dấu ngoặc đơn đóng.
Ví dụ -
'(())()' is a well-formed parentheses '())' is not a well-formed parentheses '()()()' is a well-formed parentheses
Ví dụ
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)); Đầu ra
Và đầu ra trong bảng điều khiển sẽ là -
6