//https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/
public class Solution {
    public string MinRemoveToMakeValid(string s) {
        // use a stack
        // store the index of the (
        
        // itterate through string
        // when we get to ( push index to stack
        // when we get to ), if there is an item on stack, pop
        // if there is not mark ) to remove
        var openParen = new Stack<int>();
        var indexToRemove = new List<int>();
        for (int x = 0; x < s.Length; x++)
        {
            if (s[x] == '(')
            {
                openParen.Push(x);
            }                
            else if (s[x] == ')')
            {
                if (openParen.Count == 0)
                {
                    // mark for removal
                    indexToRemove.Add(x);
                }
                else
                {
                    openParen.Pop();
                }
            }                
        }
        // any items left on stack at the end of the iterration need to be removed        
        while (openParen.Count != 0)
        {
            indexToRemove.Add(openParen.Pop());            
        }
        
        // we need to ensure we remove desc order to not ruin indexes
        indexToRemove.Sort();
        indexToRemove.Reverse();
        
        // remove any marked
        foreach (var x in indexToRemove)
        {
            s = s.Remove(x,1);
        }
        return s;      
                
    }
}