Java Simple Brute Force Solution Using Stack
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem is about finding the minimum number of parentheses that need to be added to
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem is about finding the minimum number of parentheses that need to be added to make a string of parentheses valid. A valid string means that every opening parenthesis \'(\' has a corresponding closing parenthesis \')\'.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nUse a stack to keep track of unmatched opening parentheses \'(\'.\nTraverse the string:\nIf the character is \'(\', push it onto the stack.\nIf the character is \')\', check if the stack is not empty:\nIf the stack is not empty, pop an element from the stack (indicating a match).\nIf the stack is empty, increment a counter c (indicating an unmatched closing parenthesis).\nAfter traversing the string, the size of the stack will represent the unmatched opening parentheses, and the counter c will represent the unmatched closing parentheses.\nThe result will be the sum of the stack size and the counter c.\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int minAddToMakeValid(String S) {\n        Stack s = new Stack<>();\n        int c = 0;\n        for(int i=0; i<S.length(); i++){\n            if(S.charAt(i) == \'(\'){\n                s.add(S.charAt(i));\n            }\n            else{\n                if(!s.isEmpty()){\n                    s.pop();\n                }\n                else{\n                    c++;\n                }\n            }\n        }\n        c = c + s.size();\n        return c;\n    }\n}\n```
['Java']