C++ 5 lines, O(n)
We can flip the question and ask how many "extra" parentheses the string has that makes it invalid. Then we can add (or remove) the same number of parentheses t
We can flip the question and ask how many "extra" parentheses the string has that makes it invalid. Then we can add (or remove) the same number of parentheses to make it valid.\n\nWe increment the number of  ```open``` parentheses when we see ```\'(\'```, and decrement otherwise. Every time that number is negative, that means that we have an extra ```\')\'```, and we increment ```closed```.\n\nThe result is the sum of extra open and extra closed parentheses.\n```\nint minAddToMakeValid(string S) {\n    int open = 0, closed = 0;\n    for (auto c : S) {\n      open = c == \'(\' ? max(0, open) + 1 : open - 1;\n      if (open < 0) ++closed;\n    }\n    return max(0, open) + closed;\n}\n```
[]