Explaining One Pass
It is intuitive to count ( and ) and balance them on the fly.\n\nCases like )( should be disallowed, regardless of equal counts of ( and ) .\n\nThat is, count o
It is intuitive to count `(` and `)` and balance them on the fly.\n\nCases like `)(` should be disallowed, regardless of equal counts of `(` and `)` .\n\nThat is, count of `)` should `<=` count of `(` all the time.\n\nReferring to the code, when `right_expected == 0` and we hit `)`, we ought to add a `(` in the front immediately to maintain the above invariant.\n```\n    def minAddToMakeValid(self, s: str) -> int:\n        right_expected = added = 0\n        for ch in s:\n            if ch == \'(\':\n                right_expected += 1\n            else:  # ch == \')\':  \n                if right_expected == 0:  # Extra \')\' like \'())\'\n                    added += 1  # Add (\n                else:  # right_expected > 0\n                    right_expected -= 1\n\n        return added + right_expected\n```
[]