Minimum number of deletion to make valid parentheses string

Problem: Given a string s of '(' , ')' and alphanumeric characters, write a method to remove the minimum number of parentheses ( '(' or ')' ) so that the resulting parentheses string is valid and return any valid string.

Example:

Input: s = "a(b)c)d"
Output: "a(b)cd"
Explanation: "a(b)cd" or "a(bc)d" would be the valid strings.

Approach: We can use stack here. We iterate through the whole string. Whenever we see a '(',  we push the its index to the stack and whenever we see ')', we pop from the stack. If in case of ')' the stack is empty then we know that we need to remove this ')' so we add this index to indexes to remove. We can use a set to add such indexes.

After we are done with the whole iteration, if there are any indexes remaining in the stack then that means we need to remove '(' at these indexes so we add all the indexes to the set of indexes to remove.

Now we can create another string with all the characters in the original input string except the characters at the indexes which are present in the set of indexes to remove.

That's all!

Implementation in C#:

    public string MinRemoveToMakeValid(string s) 

    {

        Stack<int> parenthesesStack = new Stack<int>();

        HashSet<int> indexToRemove = new HashSet<int>();

        for (int i = 0; i < s.Length; ++i)

        {

            if (s[i] == '(')

            {

                parenthesesStack.Push(i);

            }

            else if (s[i] == ')')

            {

                if (parenthesesStack.Count > 0)

                {

                    parenthesesStack.Pop();

                }

                else

                {

                    indexToRemove.Add(i);

                }

            }

        }

        while (parenthesesStack.Count > 0)

        {

            indexToRemove.Add(parenthesesStack.Pop());

        }

        // Using string builder as we need to append a lot of characters.

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < s.Length; ++i)

        {

            if (!indexToRemove.Contains(i))

            {

                sb.Append(s[i]);

            }

        }

        return sb.ToString();

    }

Complexity: O(n)