1249.md

1249. Minimum Remove to Make Valid Parentheses

Level:

Topic:

Similar Problem:

• 1047. Remove All Adjacent Duplicates In String

Question

Given a string s of '(' , ')' and lowercase English characters.

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

Intuition

use deque to store the valid parentheses position

• if sees open paren, addlast
• if sees close paren, peeklast if it's open, popLast
• else add close paren to deque
• lastly, whatever remains in the deque gets removed

Code

Time: O(n)
Space: O(n) for building a new string and deque

public String minRemoveToMakeValid(String s) {
    Deque<Integer> dq = new ArrayDeque<>();
    int n = s.length();
    for (int i = 0; i < n; i++) {
        char c = s.charAt(i);
        if (c == '(')
            dq.addLast(i);
        else if (c == ')') {
            if (!dq.isEmpty() && s.charAt(dq.peekLast()) == '(')
                dq.removeLast();
            else
                dq.addLast(i);
        }
    }
    if (dq.isEmpty())
        return s;

    StringBuilder ans = new StringBuilder();
    for (int i = 0; i < n; i++) {
        if (!dq.isEmpty() && dq.peekFirst() == i)
            dq.pollFirst();
        else
            ans.append(s.charAt(i));
    }
    return ans.toString();
}