1249. Minimum Remove to Make Valid Parentheses LeetCode Solution

Last updated: February 22, 2025

In this guide, you will get 1249. Minimum Remove to Make Valid Parentheses LeetCode Solution with the best time and space complexity. The solution to Minimum Remove to Make Valid Parentheses problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Remove to Make Valid Parentheses solution in C++
Minimum Remove to Make Valid Parentheses solution in Java
Minimum Remove to Make Valid Parentheses solution in Python
Additional Resources

1249. Minimum Remove to Make Valid Parentheses LeetCode Solution image

Problem Statement of Minimum Remove to Make Valid Parentheses

Given a string s of ‘(‘ , ‘)’ and lowercase English characters.
Your task is to remove the minimum number of parentheses ( ‘(‘ or ‘)’, in any positions ) so that the resulting parentheses string is valid and return any valid string.
Formally, a parentheses string is valid if and only if:

It is the empty string, contains only lowercase characters, or
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.

Example 1:

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.

Example 2:

Input: s = “a)b(c)d”
Output: “ab(c)d”

Example 3:

Input: s = “))((”
Output: “”
Explanation: An empty string is also valid.

Constraints:

1 <= s.length <= 105
s[i] is either '(' , ')', or lowercase English letter.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

1249. Minimum Remove to Make Valid Parentheses LeetCode Solution in C++

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 the unpaired '(' index.
      } else if (s[i] == ')') {
        if (stack.empty())
          s[i] = '*';  // Mark the unpaired ')' as '*'.
        else
          stack.pop();  // Find a pair!
      }

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

    std::erase(s, '*');
    return s;
  }
};
/* code provided by PROGIEZ */

1249. Minimum Remove to Make Valid Parentheses LeetCode Solution in Java

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 the unpaired '(' index.
      } else if (sb.charAt(i) == ')') {
        if (stack.isEmpty())
          sb.setCharAt(i, '#'); // Mark the unpaired ')' as '#'.
        else
          stack.pop(); // Find a pair!
      }

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

    return sb.toString().replaceAll("#", "");
  }
}
// code provided by PROGIEZ

1249. Minimum Remove to Make Valid Parentheses LeetCode Solution in Python

class Solution:
  def minRemoveToMakeValid(self, s: str) -> str:
    stack = []  # unpaired '(' indices
    chars = list(s)

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

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

    return ''.join(chars).replace('*', '')
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents