✅Beats 100% | GREEDY | JAVA | Explained🔥🔥🔥
Approach:\nWe can iterate through the string and track the unmatched parentheses. \nSpecifically, we\'ll count:\n\nUnmatched opening brackets: These are ( for w
**Approach:**\nWe can iterate through the string and track the unmatched parentheses. \nSpecifically, we\'ll count:\n\n**Unmatched opening brackets:** These are ( for which we haven\'t yet found a matching ).\n**Unmatched closing brackets:** These are ) that don\'t have an opening bracket ( before them.\n\n**Plan:**\n\n**We use two variables:**\nopen_needed: Keeps track of how many opening parentheses we need to match closing parentheses.\nclose_needed: Keeps track of how many closing parentheses we need.\n\n**Traverse the string:**\nIf we encounter (, it means we will need a closing parenthesis later, so we increase the close_needed count.\n\n**If we encounter ):**\nIf there\'s a corresponding opening ( (i.e., close_needed > 0), we decrease the close_needed.\nIf not (i.e., close_needed == 0), we need an additional opening ( to match this closing bracket, so we increase open_needed.\nAt the end of the traversal, the total number of moves will be the sum of open_needed (missing opening brackets) and close_needed (missing closing brackets).\n\n**Time Complexity:**\nThe time complexity is O(n) where n is the length of the string, as we process each character once.\n\n**Space Complexity:**\nThe space complexity is O(1) as we only use a few integer variables to track the counts.\nThis approach efficiently calculates the minimum number of moves to make the string valid.\n# Code\n```java []\nclass Solution {\n    public int minAddToMakeValid(String s) {\n        int open_needed = 0;   // To track unmatched opening \'(\'\n        int close_needed = 0;  // To track unmatched closing \')\'\n        \n        for (char c : s.toCharArray()) {\n        if (c == \'(\') {\n            close_needed++;  // We need a closing \')\' for every \'(\'\n        } else if (c == \')\') {\n            if (close_needed > 0) {\n                close_needed--;  // Found a matching \'(\' for the \')\'\n            } else {\n                open_needed++;  // We need an extra \'(\' to match this \')\'\n            }\n        }\n    }\n    return open_needed + close_needed;\n    }\n}\n```
['Java']