Find valid string after removing minimum number of invalid parentheses - mock interview as interviewee - 8:00 PM - Oct. 4, 2020

FindValidStringAfterRemoveMinimum.cs

// Given a string s of '(' , ')' and lowercase English characters. Remove the minimum number of parenthesis to make the parentheses in the string valid.
// 
// s = "a)b(c)d"
// res = "ab(c)d"
// VALID - isValid
// ( -> INDEX ) -> valid string -> 
//     openPara
    
//     ((( -> 
//        ()()(
//        (()()
//        -- -
        
// bfs -> VALID BRUTE FORCE 
// ONCE - SHOULD BE Minimum number
// BFS -> 
// ()() -> ok 
// (() -> remove one, index 0 or 1 -> find valid (), remove open
// ()(( -> remove two, 
// check not valid
// 0 )((  -> queue
// 1 (((  
// 2 ()(
// 3 ()( ->    
// ------------------------    
// 0 )((  -> queue
// 1 (((  
// 2 () ->
// 3 ()( ->    
()()))
    --
)()))
-  --
remove minimum number parenthese - remove all valid 
find one -> make it quick and short -> 
// ----------------------     
string FindMinimumNumberToRemove(string s)     
{
    if(s == null || s.Length == 0)
        return 0; 
    
    if(isValid(s))
    {
        return 0; 
    }
    
    // queue - BFS - save index position of open or close parentheses
    // index - int[], size - 2, index position - second - 0, close 1
    // Tuple<string, int>
    var queue = new Queue<Tuple<string, int>>(); 
    queue.Enqueue(new Tuple<string,int>(s, 0)); 
    int index = 1; 
    // (a)b)
    // ()((
    //  - 
    // ((((((( -> 
    // O(m * m * N * N) - 
    // m is how many strings (count of parenthese), n is size of string - 4
    // space -> queue O(m! * n) - m is count of parent chars in string 
    // m + m*(m-1) + m(m-1)(m-2) + ... + m!
    // m* m!= (m+1)! loosely upper bound
    // 10 -> 10*9 -> 10*9*8 
    // 10 -> 10: 9 -> 90: 8
    while(queue.Count > 0)
    {
        // BFS  - every string will be check - O(m) count of parenthese < N
        var count = queue.Count; 
        
        for(int i = 0; i < count; i++)
        {
            //(a)b)
            var current = queue.Dequeue(); 
            var item1 = current.Item1;
            var item2 = current.Item2;
            
            //  O(N * N)
            for(int j = item2; j < current.Length; j++) // (
            {
                var c = current[j];
                var isPare = c == '(' || c== ')';
                
                if(isPare)
                {
                    var tmp = current.RemoveAt(j);
                    if(isValid(tmp)
                   {
                       return tmp; 
                   }
                   else 
                   {  // one char shorter 
                      queue.Enqueue(new Tuple<string, int>(tmp, j)); 
                   }
               }                       
            }            
        }
        
        index++;                  
    }    
}

// O(N) - N length of S                       
private bool isValid(string s)
{
  if(s == null || s.Length == 0)
    return true;
                           
  int openCount = 0;                           
                           
  for(int i = 0; i < s.Length; i++)
  {
     var c = s[i];
     if(c == '(')
     {
      openCount++;
     }
     else if(c == ')')
     {
        if(openCount == 0)
        {
          return false;
        }
                                   
        openCount--; 
     }
  }
                           
  return openCount == 0; 
}