Cho chuỗi s gồm '(', ')' và chữ cái thường. Xóa số lượng dấu ngoặc tối thiểu (ở bất kỳ vị trí nào) để chuỗi ngoặc kết quả hợp lệ. Chuỗi ngoặc hợp lệ khi: rỗng, chỉ chứa chữ cái, hoặc dạng AB (A+B hợp lệ), hoặc dạng (A) với A hợp lệ.
Ví dụ: "a)b(c)d" -> "ab(c)d".
Giải pháp dùng stack:
Duyệt chuỗi, gặp '(' đẩy chỉ số vào stack.
Gặp ')': nếu stack không rỗng pop, ngược lại đánh dấu '*' (xóa).
Sau duyệt, các chỉ số còn lại trong stack đánh dấu '*'.
Xây dựng chuỗi kết quả bỏ qua ký tự '*'.
Ví dụ hoàn chỉnh
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string minRemoveToMakeValid(string s) {
stack<int> st;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') st.push(i);
else if (s[i] == ')') {
if (!st.empty()) st.pop();
else s[i] = '*';
}
}
while (!st.empty()) {
s[st.top()] = '*';
st.pop();
}
string ans = "";
for (int i = 0; i < s.size(); i++) {
if (s[i] != '*') ans += s[i];
}
return ans;
}
};
int main() {
Solution ob;
cout << (ob.minRemoveToMakeValid("a)b(c)d"));
}
Input
"a)b(c)d"
Output
ab(c)d