[Java/Python 3] two one pass codes - space O(n) and O(1), respectively
Intuition:\n\nWe only need to count those unmatched parentheses. \nKey Observation:\n\nAfter removal of matched parentheses, the remainings must be ))...)(...((
**Intuition:**\n\nWe only need to count those unmatched parentheses. \n**Key Observation:**\n\nAfter removal of matched parentheses, the remainings must be `))...)(...(`(both numbers of open and close patheses can be `0`). Otherwise, there would be at least one pair of `()`.\n\n**Algorithm Description:**\n\nLoop through the input array.\n1. if encounter \'(\', push \'(\' into stack;\n2. otherwise, \')\', check if there is a matching \'(\' on top of stack; if no, increase the counter by 1; if yes, pop it out;\n3. after the loop, count in the un-matched characters remaining in the stack.\n\n\nMethod 1: \nTime & space: O(n).\n```java\n    public int minAddToMakeValid(String S) {\n        Deque<Character> stk = new ArrayDeque<>();\n        int count = 0;\n        for (char c : S.toCharArray()) {\n            if (c == \'(\') { \n                stk.push(c); \n            }else if (stk.isEmpty()) { \n                ++count; \n            }else { \n                stk.pop(); \n            }\n        }\n        return count + stk.size();\n    }\n```\nor, make the above the code shorter:\n\n```java\n    public int minAddToMakeValid(String S) {\n        Deque<Character> stk = new ArrayDeque<>();\n        for (char c : S.toCharArray()) {\n            if (c == \')\' && !stk.isEmpty() && stk.peek() == \'(\') { // pop out matched pairs.\n                stk.pop();  \n            }else { // push in unmatched chars.\n                stk.push(c); \n            } \n        }\n        return stk.size();\n    }\n```\nMethod 2: \nSince there is only one kind of char, \'(\', in stack,only a counter will also work.\nTime: O(n),  space: O(1).\n\n\n```java\n    public int minAddToMakeValid(String S) {\n        int count = 0, stk = 0;\n        for (int i = 0; i < S.length(); ++i) {\n            if (S.charAt(i) == \'(\') { \n                ++stk; \n            }else if (stk == 0) { \n                ++count; \n            }else {\n                --stk; \n            }\n        }\n        return count + stk;\n    }\n```\n```python\n    def minAddToMakeValid(self, S: str) -> int:\n        stk = count = 0\n        for c in S:\n            if c == \'(\':\n                stk += 1\n            elif stk > 0:\n                stk -= 1    \n            else:\n                count += 1\n        return stk + count\n```\n\nSome may like variable namings such as `open` and `close` brackets, here are the corresponding codes:\n```java\n    public int minAddToMakeValid(String s) {\n        int unmatchedOpenBrackets = 0, unmatchedCloseBrackets = 0;\n        for (int i = 0; i < s.length(); ++i) {\n            if (s.charAt(i) == \'(\') {\n                ++unmatchedOpenBrackets;\n            }else if (unmatchedOpenBrackets > 0) {\n                --unmatchedOpenBrackets;\n            }else {\n                ++unmatchedCloseBrackets;\n            }\n        }\n        return unmatchedOpenBrackets + unmatchedCloseBrackets;\n    }\n```\n\n```python\n    def minAddToMakeValid(self, S: str) -> int:\n        unmatched_open_brackets = unmatched_close_brackets = 0\n        for c in S:\n            if c == \'(\':\n                unmatched_open_brackets += 1\n            elif unmatched_open_brackets > 0:\n                unmatched_open_brackets -= 1    \n            else:\n                unmatched_close_brackets += 1\n        return unmatched_open_brackets + unmatched_close_brackets\n```\n\n
[]