Detailed explanation - O(n) | O(1) - Python, C++
Intuition\nLet the level at position i be the number of opening parentheses ( minus number of closing parentheses ) in prefix up to i-th char inclusively. The s
# Intuition\nLet the level at position `i` be the number of opening parentheses `(` minus number of closing parentheses `)` in prefix up to `i`-th char inclusively. The string is invalid if and only if this level falls below zero somewhere or it\'s not zero at the end of the string.\n\n# Approach\nIf we encounter the position where the level is below zero we can raise the level on the whole string by adding some opening parentheses at the very beginning of the string. Say we have string `str`:\n\n```\npos:      0  1  2  3  4  5  6  7\nstr:      (  (  )  )  )  (  )  )\nlvl:   0  1  2  1  0 -1  0 -1 -2\n```\n\nHow many parentheses we should add at the beginning of the string? We want to avoid falling level below zero on the positions 4, 6, 7 and on posisition 7 the level reaches it\'s minimum -2. So we want to add exactly 2 opening parentheses:\n\n```\npos:      0  1  2  3  4  5  6  7\nstr:      (  (  (  (  )  )  )  (  )  )\nlvl:   0  1  2  3  4  3  2  1  2  1  0\n``` \n\nThe second case of string invalidation is when the parentheses sequence isn\'t closed properly. Look at another example `str`:\n\n```\npos:      0  1  2  3  4  5\nstr:      (  )  )  )  (  (\nlvl:   0  1  0 -1 -2 -1  0\n```\n\nFirst, we don\'t want level to fall below zero so we add two `(`:\n\n```\npos:      0  1  2  3  4  5  6  7\nstr:      (  (  (  )  )  )  (  (\nlvl:   0  1  2  3  2  1  0  1  2\n```\n\nAnd now we see clearly we should add two `)` at the end to make parenthese close:\n\n```\npos:      0  1  2  3  4  5  6  7  8  9\nstr:      (  (  (  )  )  )  (  (  )  )\nlvl:   0  1  2  3  2  1  0  1  2  1  0\n```\n\n# Algorithm\n\n1. Find minimum level `min_lvl`. Initially `min_lvl = lvl = 0`;\n2. Raise the level at the whole string by adding `-min_lvl` opening parentheses at the beginning. If it\'s zero it\'s zero);\n3. Look at the level at the end: we raise it by `-min_lvl` and now `lvl >= 0` but we should make `lvl = 0`. To do so we add `lvl` closing paretheses at the end.\n4. Total number of added parentheses is `-min_lvl + (lvl + -min_lvl)`\n\n# Complexity\n- Time complexity:\n$O(n)$ \n- Space complexity:\n$O(1)$\n\n# Code\n```python3 []\nclass Solution:\n    def minAddToMakeValid(self, s: str) -> int:\n        lvl = 0\n        min_lvl = 0\n        for c in s:\n            if c == \'(\':\n                lvl += 1\n            else:\n                lvl -= 1\n                min_lvl = min(min_lvl, lvl)\n        moves = 0\n        if min_lvl < 0:\n            lvl += -min_lvl\n            moves += -min_lvl\n        return moves + lvl\n\n```\n\n```cpp []\nclass Solution {\npublic:\n    int minAddToMakeValid(string s) {\n        int lvl = 0, min_lvl = 0;\n        for (char c: s) {\n            if (c == \'(\') {\n                lvl++;\n            } else {\n                lvl--;\n                min_lvl = min(min_lvl, lvl);\n            }\n        }\n        int moves = 0;\n        if (min_lvl < 0) {\n            lvl += -min_lvl;\n            moves += -min_lvl;\n        }\n        return moves + lvl;\n    }\n};\n```
['String', 'C++', 'Python3']