[C++/Java/Python] Straight Forward One Pass
Intuition:\nTo make a string valid,\nwe can add some ( on the left,\nand add some ) on the right.\nWe need to find the number of each.\n\n\n## Explanation:\nlef
## **Intuition**:\nTo make a string valid,\nwe can add some `(` on the left,\nand add some `)` on the right.\nWe need to find the number of each.\n<br>\n\n## **Explanation**:\n`left` records the number of `(` we need to add on the left of `S`.\n`right` records the number of `)` we need to add on the right of `S`,\nwhich equals to the number of current opened parentheses.\n<br>\n\nLoop char `c` in the string `S`:\n`if (c == \'(\')`, we increment `right`,\n`if (c == \')\')`, we decrement `right`.\nWhen `right` is already 0, we   increment `left`\nReturn `left + right` in the end\n<br>\n\n## **Time Complexity**:\nTime `O(N)`\nSpace `O(1)`\n<br>\n\n**Java:**\n```java\n    public int minAddToMakeValid(String S) {\n        int left = 0, right = 0;\n        for (int i = 0; i < S.length(); ++i) {\n            if (S.charAt(i) == \'(\') {\n                right++;\n            } else if (right > 0) {\n                right--;\n            } else {\n                left++;\n            }\n        }\n        return left + right;\n    }\n```\n\n**C++:**\n```cpp\n    int minAddToMakeValid(string S) {\n        int left = 0, right = 0;\n        for (char c : S)\n            if (c == \'(\')\n                right++;\n            else if (right > 0)\n                right--;\n            else\n                left++;\n        return left + right;\n    }\n```\n\n**Python:**\n```python\n    def minAddToMakeValid(self, S):\n        left = right = 0\n        for i in S:\n            if right == 0 and i == \')\':\n                left += 1\n            else:\n                right += 1 if i == \'(\' else -1\n        return left + right\n```\n
[]