Introduction

In this article, we will see about Minimum Remove to Make Valid Parentheses. We have to remove the minimum number of parentheses to make a string with valid parentheses.

BACKGROUND

Day 15 of 100 Days of Leetcode Programming Challenge. This problem tests our knowledge in the Stack data structure.

LANGUAGE

I took C# programming language to solve this problem. Since language is independent of the problem. You can use whatever language you wish to solve. Only problem solving approach(logic) is important.

Let’s jump into interesting problem,

Problem

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.

Example 4:

Input: s = "(a(b(c)d)"
Output: "a(b(c)d)"

Constraints:

  • 1 <= s.length <= 10^5
  • s[i] is one of  '(' , ')' and lowercase English letters.

Solution Approach

  1. This time, I just thought to play by introducing user-defined class, OpenBracketWithIndex
public class OpenBracketWithIndex
{
    public int Index;
    public char OpenBracket;
    public OpenBracketWithIndex(int index,char openBracket)
    {
        Index = index;
        OpenBracket = openBracket;
    }
}

This OpenBracketWithIndex class, contains the open parenthesis with its specific index.

2. I asked Stack to contain the OpenBracketWithIndex as its type.

3. I used StringBuilder to process the data.

4. Whenever I get ‘(‘ – open bracket, I append it in stringbuilder and push into stack with its index at stringbuilder.

5. Whenever I get ‘)’ – close bracket, I check whether open bracket already came, by using stack. If it does, then this is a valid close bracket. So I append it in StringBuilder and pop out the open bracket from the stack.

6. Whenever I get character, I just append it in StringBuilder.

7. Closely look at my solution, to understand better😃

Solution

  public class Solution 
  {

    public string MinRemoveToMakeValid(string s) {
        
        StringBuilder sb = new StringBuilder();
        
        Stack<OpenBracketWithIndex> stack = new Stack<OpenBracketWithIndex>();
        
        for(int i=0;i<s.Length;i++)
        {
            if(s[i] == '(')
            {
                sb.Append(s[i]);
                 stack.Push(new OpenBracketWithIndex(sb.Length-1,s[i]));
            }
            else if(s[i] == ')')
            {
                if(stack.Any())
                {
                    sb.Append(')');
                    stack.Pop();
                }
            }
            else 
            {
                sb.Append(s[i]);
            }
        }
        while(stack.Any())
        {
            var res = stack.Pop();
            int index = res.Index;
            sb.Remove(index,1);
        }
        return sb.ToString();
    }
}
public class OpenBracketWithIndex
{
    public int Index;
    public char OpenBracket;
    public OpenBracketWithIndex(int index,char openBracket)
    {
        Index = index;
        OpenBracket = openBracket;
    }
}

Time Complexity: O(n)

Space Complexity : O(n)