Easy to Understand || ✅Beats 100% || C++, Python, Java
IntuitionApproachComplexity
Time complexity: O(n)

Space complexity: O(n)
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity: $$O(n)$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(n)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    int minAddToMakeValid(string s) {
        int count = 0;
        stack<int> st;

        for (int i=0; i<s.length(); i++) {
            if (s[i] == '(') {
                st.push(i);
            }
            else{
                if (!st.empty()) {
                    st.pop();
                }
                else{
                    count += 1;
                }
            }
        }
        if (!st.empty()){
            count += st.size();
        }
        return count;
    }
};


```
```python3 []
class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        count = 0
        stack = []
        for i in range(len(s)):
            if s[i] == "(":
                stack.append(i)
            else:
                if stack:
                    stack.pop()
                else:
                    count += 1
            
        if stack:
            count += len(stack)

        return count


```
```java []
class Solution {
    public int minAddToMakeValid(String s) {
        int count = 0;
        Stack<Integer> st = new Stack<Integer>();

        for (int i=0; i<s.length(); i++) {
            if (s.charAt(i) == '(') {
                st.push(i);
            }
            else{
                if (!st.empty()) {
                    st.pop();
                }
                else{
                    count++;
                }
            }
        }
        if (!st.empty()){
            count = count + st.size();
        }
        return count;
    }
}


```
['String', 'Stack', 'C++', 'Java', 'Python3']