Skip to content

1249. Minimum Remove to Make Valid Parentheses 👍

  • Time: $O(|\texttt{s}|)$
  • Space: $O(|\texttt{s}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  string minRemoveToMakeValid(string s) {
    stack<int> stack;  // Unpaired '(' indices

    for (int i = 0; i < s.length(); ++i)
      if (s[i] == '(') {
        stack.push(i);  // Record unpaired '(' index
      } else if (s[i] == ')') {
        if (stack.empty())
          s[i] = '*';  // Mark unpaired ')' as '*'
        else
          stack.pop();  // Find a pair!
      }

    // Mark unpaired '(' as '*'
    while (!stack.empty())
      s[stack.top()] = '*', stack.pop();

    s.erase(remove(begin(s), end(s), '*'), end(s));
    return s;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public String minRemoveToMakeValid(String s) {
    Deque<Integer> stack = new ArrayDeque<>(); // Unpaired '(' indices
    StringBuilder sb = new StringBuilder(s);

    for (int i = 0; i < s.length(); ++i)
      if (sb.charAt(i) == '(') {
        stack.push(i); // Record unpaired '(' index
      } else if (sb.charAt(i) == ')') {
        if (stack.isEmpty())
          sb.setCharAt(i, '#'); // Mark unpaired ')' as '#'
        else
          stack.pop(); // Find a pair!
      }

    // Mark unpaired '(' as '#'
    while (!stack.isEmpty())
      sb.setCharAt(stack.pop(), '#');

    return sb.toString().replaceAll("#", "");
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def minRemoveToMakeValid(self, s: str) -> str:
    stack = []  # Unpaired '(' indices
    chars = [c for c in s]

    for i, c in enumerate(chars):
      if c == '(':
        stack.append(i)  # Record unpaired '(' index
      elif c == ')':
        if stack:
          stack.pop()  # Find a pair
        else:
          chars[i] = '*'  # Mark unpaired ')' as '*'

    # Mark unpaired '(' as '*'
    while stack:
      chars[stack.pop()] = '*'

    return ''.join(chars).replace('*', '')