Straightforward C++ (0 ms), O(N), with explanation
The idea is to keep track of number of unused \'(\' in addition to keep track of extra \')\'\nSo lets say we  use open and cnt variables for this goal, respecti
The idea is to keep track of number of unused \'(\' in addition to keep track of extra \')\'\nSo lets say we  use open and cnt variables for this goal, respectively.\nMove forward through the string. \n* Once you reach a \'(\' , increament the open variable.\n* Once you reach the \')\', \n\t* If the open variable is equal to zero, that means the current \')\' is extra and we need one \')\' before the current position. Like if the strign is "( ) **)**". For the second \')\', we need to have a \'(\' before it, so increment the cnt.\n\t* If open variable is a positive number, means we have already visited some \'(\' which is not used yet. so lets decremenat open variable\n\nFInally we return sum of open and cnt variables.\n\n```\nint minAddToMakeValid(string S) {\n  int len = S.length();\n  if (len<=1)\n      return len;\n  int op=0;        \n  int cnt=0;\n  for (int i=0;i<len; ++i){\n      if (S[i]==\'(\' )        op++;  \n      else {\n          if (op==0)         cnt++;  /*we rached an extra \')\' */\n          else {             op--;        /*use one of previously visited \'(\' */\n          }\n      }\n  }\n  return  (cnt+op);\n}\n```\n
[]