using System;

using System.Collections.Generic;

using System.Text;

public class Program

{

    public static void Main()

    {

        string s = "lee(t(c)o)de)";

        string expected = "lee(t(c)o)de";

        //string result = MinRemoveToMakeValid(s);

        string result = MinRemoveToMakeValidBest(s);

        Console.WriteLine("result: {0}", result);

        Console.WriteLine("expected: {0}", expected);

    }

​

    public static string MinRemoveToMakeValidBest(string s) {

        var parens = new Stack<int>();

        var sb = new StringBuilder();

        bool[] invalid = new bool[s.Length];

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

        {

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

                parens.Push(i);

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

            {

                if (parens.Count > 0)

                    parens.Pop();

                else

                    invalid[i] = true;

            }

        }

        while (parens.Count > 0)

        {

            invalid[parens.Pop()] = true;

        }

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

        {

            if (!invalid[i])

                sb.Append(s[i]);

        }

        return sb.ToString();

    }

    public static string MinRemoveToMakeValid(string s) {

        Stack parens = new Stack(); // ((())()()((

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

        {

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

                parens.Push(s[i]);

            }

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

            {

                if (parens.Pop() == null) {

                    s = s.Remove(i, 1);

                    i--;

                }

            }

        }

        if (!parens.isEmpty())

        {            

            parens = new Stack();

            for (int i = s.Length - 1; i >= 0; i--)

            {

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

                    parens.Push(s[i]);

                }

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

                {

                    if (parens.Pop() == null) {

                        s = s.Remove(i, 1);

                    }

                }

            }

        }

        return s;

    }

    public class Stack

    {

        ListNode head;

        public Stack()

        {

            head = new ListNode();

        }

        public ListNode Pop()

        {

            ListNode temp = head.next;

            if (head.next != null)

                head.next = head.next.next;

            return temp;

        }

        public void Push(char val)

        {

            ListNode newNode = new ListNode();

            newNode.val = val;

            newNode.next = head.next;

            head.next = newNode;

        }

        public bool isEmpty()

        {

            return head.next == null;

        }

    }

    public class ListNode

    {

        public char val;

        public ListNode next;

    }

}

​

// start 2:33pm

// finish 3:44pm

​

// if we encounter '(' then ...

    // add to '(' stack

​

// if we encounter ')' then ...

    // if pop of '(' stack is not null then i++

    // else remove ')' character from string

​

// if we get to end of string and '(' stack is not empty then ...

// traverse string again in reverse order, process with reverse algorithm

​