Simple Java Code ☠️
Code\njava []\nclass Solution {\n    public int minAddToMakeValid(String s) {\n        int n = s.length();\n        Stack<Character> stack = new Stack<>();\n   
# Code\n```java []\nclass Solution {\n    public int minAddToMakeValid(String s) {\n        int n = s.length();\n        Stack<Character> stack = new Stack<>();\n        for(int i=0;i<n;i++){\n            if(s.charAt(i) == \'(\'){\n                stack.push(\'(\');\n            }\n            else{\n                if(!stack.isEmpty() && stack.peek() == \'(\'){\n                    stack.pop();\n                }\n                else{\n                    stack.push(\')\');\n                }\n            }\n        }\n        return stack.size();\n    }\n}\n```\n\n\n### Explanation:\n\n1. **Initialize a Stack:**\n   - The stack will help track unmatched parentheses. We push opening parentheses `(` when we see them and try to match them with closing parentheses `)`.\n\n2. **Iterate Through the String:**\n   - The loop goes through each character of the string one by one.\n\n3. **Handling Opening Parentheses `(`:**\n   - If we encounter an opening parenthesis `(`, we simply push it onto the stack. This is because we need to find a closing parenthesis `)` to match it later.\n\n4. **Handling Closing Parentheses `)`**:\n   - If we encounter a closing parenthesis `)`, we check whether the top of the stack is an opening parenthesis `(`. If the top of the stack is `(`, it means we found a matching pair, so we pop the stack to remove the matched `(`.\n   - If the stack is either empty or the top of the stack is not `(`, it means that we don\u2019t have an unmatched opening parenthesis to balance the current `)`. In this case, we push the `)` onto the stack, indicating an unmatched closing parenthesis.\n\n5. **End of the Loop:**\n   - By the end of the loop, the stack contains only unmatched parentheses (both opening `(` and closing `)` parentheses that couldn\u2019t be balanced).\n   - The size of the stack tells us how many moves are required to make the string valid, as each unmatched parenthesis needs a corresponding matching one to become balanced.\n\n6. **Return the Stack Size:**\n   - Finally, we return the size of the stack, which represents the minimum number of insertions needed to make the parentheses string valid.\n\n### Example:\n\n- Input: `"())"`\n  - At index 0: We encounter `(` \u2192 Push `(` onto the stack.\n  - At index 1: We encounter `)` \u2192 The top of the stack is `(`, so we pop the stack to balance this pair.\n  - At index 2: We encounter `)` \u2192 The stack is empty, so we push `)` onto the stack.\n\n  Stack: `[\')\']`\n\n  The stack contains 1 unmatched closing parenthesis, so we return `1`.\n\n- Input: `"((("`\n  - At each index (0, 1, 2), we encounter `(` and push them onto the stack.\n\n  Stack: `[\'(\', \'(\', \'(\']`\n\n  The stack contains 3 unmatched opening parentheses, so we return `3`.\n\n### Time Complexity:\n- **Time Complexity:** The time complexity is **O(n)**, where `n` is the length of the string. This is because we iterate through the string once and perform constant-time operations for each character.\n  \n- **Space Complexity:** The space complexity is **O(n)** in the worst case, where all parentheses are unmatched and stored in the stack. \n\n\n\n\n\n\n\n
['String', 'Stack', 'Java']