✅ Beats 100% | Working 08.10.2024 | Explained step by step
python3 []\nclass Solution:\n    def minAddToMakeValid(self, s: str) -> int:\n        # Initialize the counter for minimum additions needed\n        ans = 0\n  
```python3 []\nclass Solution:\n    def minAddToMakeValid(self, s: str) -> int:\n        # Initialize the counter for minimum additions needed\n        ans = 0\n        \n        # Initialize the balance of parentheses (open - close)\n        bal = 0\n\n        # Iterate through each character in the string\n        for ch in s:\n            if ch == \'(\':\n                # If it\'s an opening parenthesis, increment the balance\n                bal += 1\n            else:\n                # If it\'s a closing parenthesis, decrement the balance\n                bal -= 1\n\n            # If balance becomes negative (more closing than opening parentheses)\n            if bal < 0:\n                # Add the absolute value of balance to answer\n                # This represents the number of opening parentheses we need to add\n                ans += -bal\n                # Reset balance to 0 since we\'ve accounted for the imbalance\n                bal = 0\n\n        # After processing all characters, add any remaining open parentheses\n        # This represents the number of closing parentheses we need to add\n        ans += bal\n\n        # Return the minimum number of additions needed to make the string valid\n        return ans\n```\n```cpp []\n#include <string>\n\nclass Solution {\npublic:\n    int minAddToMakeValid(std::string s) {\n        // \'need\' represents the number of closing parentheses \')\' needed\n        // to balance the opening parentheses \'(\'\n        int need = 0;\n\n        // \'res\' keeps track of the minimum number of parentheses\n        // that need to be added to make the string valid\n        int res = 0;\n\n        // Iterate through each character in the input string\n        for (char p : s) {\n            if (p == \'(\') {\n                // If we encounter an opening parenthesis,\n                // we increase the need for a closing parenthesis\n                need++;\n            }\n            \n            if (p == \')\') {\n                // If we encounter a closing parenthesis,\n                // we decrease the need (as it matches an opening parenthesis)\n                need--;\n\n                // If \'need\' becomes -1, it means we have an extra closing parenthesis\n                // that doesn\'t match any opening parenthesis\n                if (need == -1) {\n                    // We need to add an opening parenthesis to balance this\n                    res++;\n                    // Reset \'need\' to 0 as we\'ve handled this imbalance\n                    need = 0;\n                }\n            }\n        }\n\n        // The final result is the sum of:\n        // 1. \'res\': the number of parentheses we needed to add for balancing extra closing parentheses\n        // 2. \'need\': the number of closing parentheses we still need to add to balance remaining opening parentheses\n        return res + need;\n    }\n};\n```\n```java []\nclass Solution {\n    public int minAddToMakeValid(String s) {\n        // Initialize the counter for minimum additions needed\n        int ans = 0;\n        \n        // Initialize the balance of parentheses (open - close)\n        int bal = 0;\n        \n        // Iterate through each character in the string\n        for (char ch : s.toCharArray()) {\n            if (ch == \'(\') {\n                // If it\'s an opening parenthesis, increment the balance\n                bal++;\n            } else {\n                // If it\'s a closing parenthesis, decrement the balance\n                bal--;\n            }\n            \n            // If balance becomes negative (more closing than opening parentheses)\n            if (bal < 0) {\n                // Add the absolute value of balance to answer\n                // This represents the number of opening parentheses we need to add\n                ans += -bal;\n                // Reset balance to 0 since we\'ve accounted for the imbalance\n                bal = 0;\n            }\n        }\n        \n        // After processing all characters, add any remaining open parentheses\n        // This represents the number of closing parentheses we need to add\n        ans += bal;\n        \n        // Return the minimum number of additions needed to make the string valid\n        return ans;\n    }\n}\n```\n```golang []\npackage main\n\nfunc minAddToMakeValid(s string) int {\n    // Initialize the counter for minimum additions needed\n    ans := 0\n    \n    // Initialize the balance of parentheses (open - close)\n    bal := 0\n    \n    // Iterate through each character in the string\n    for _, ch := range s {\n        if ch == \'(\' {\n            // If it\'s an opening parenthesis, increment the balance\n            bal++\n        } else {\n            // If it\'s a closing parenthesis, decrement the balance\n            bal--\n        }\n        \n        // If balance becomes negative (more closing than opening parentheses)\n        if bal < 0 {\n            // Add the absolute value of balance to answer\n            // This represents the number of opening parentheses we need to add\n            ans += -bal\n            // Reset balance to 0 since we\'ve accounted for the imbalance\n            bal = 0\n        }\n    }\n    \n    // After processing all characters, add any remaining open parentheses\n    // This represents the number of closing parentheses we need to add\n    ans += bal\n    \n    // Return the minimum number of additions needed to make the string valid\n    return ans\n}\n```\n```javascript [JS]\n/**\n * @param {string} s\n * @return {number}\n */\nvar minAddToMakeValid = function(s) {\n    // Initialize the counter for minimum additions needed\n    let ans = 0;\n    \n    // Initialize the balance of parentheses (open - close)\n    let bal = 0;\n    \n    // Iterate through each character in the string\n    for (let ch of s) {\n        if (ch === \'(\') {\n            // If it\'s an opening parenthesis, increment the balance\n            bal++;\n        } else {\n            // If it\'s a closing parenthesis, decrement the balance\n            bal--;\n        }\n        \n        // If balance becomes negative (more closing than opening parentheses)\n        if (bal < 0) {\n            // Add the absolute value of balance to answer\n            // This represents the number of opening parentheses we need to add\n            ans += -bal;\n            // Reset balance to 0 since we\'ve accounted for the imbalance\n            bal = 0;\n        }\n    }\n    \n    // After processing all characters, add any remaining open parentheses\n    // This represents the number of closing parentheses we need to add\n    ans += bal;\n    \n    // Return the minimum number of additions needed to make the string valid\n    return ans;\n};\n```\n```typescript [TS]\nfunction minAddToMakeValid(s: string): number {\n    // Initialize the counter for minimum additions needed\n    let ans: number = 0;\n    \n    // Initialize the balance of parentheses (open - close)\n    let bal: number = 0;\n    \n    // Iterate through each character in the string\n    for (let ch of s) {\n        if (ch === \'(\') {\n            // If it\'s an opening parenthesis, increment the balance\n            bal++;\n        } else {\n            // If it\'s a closing parenthesis, decrement the balance\n            bal--;\n        }\n        \n        // If balance becomes negative (more closing than opening parentheses)\n        if (bal < 0) {\n            // Add the absolute value of balance to answer\n            // This represents the number of opening parentheses we need to add\n            ans += -bal;\n            // Reset balance to 0 since we\'ve accounted for the imbalance\n            bal = 0;\n        }\n    }\n    \n    // After processing all characters, add any remaining open parentheses\n    // This represents the number of closing parentheses we need to add\n    ans += bal;\n    \n    // Return the minimum number of additions needed to make the string valid\n    return ans;\n}\n```\n```csharp []\npublic class Solution {\n    public int MinAddToMakeValid(string s) {\n        // Initialize the counter for minimum additions needed\n        int ans = 0;\n        \n        // Initialize the balance of parentheses (open - close)\n        int bal = 0;\n        \n        // Iterate through each character in the string\n        foreach (char ch in s) {\n            if (ch == \'(\') {\n                // If it\'s an opening parenthesis, increment the balance\n                bal++;\n            } else {\n                // If it\'s a closing parenthesis, decrement the balance\n                bal--;\n            }\n            \n            // If balance becomes negative (more closing than opening parentheses)\n            if (bal < 0) {\n                // Add the absolute value of balance to answer\n                // This represents the number of opening parentheses we need to add\n                ans += -bal;\n                // Reset balance to 0 since we\'ve accounted for the imbalance\n                bal = 0;\n            }\n        }\n        \n        // After processing all characters, add any remaining open parentheses\n        // This represents the number of closing parentheses we need to add\n        ans += bal;\n        \n        // Return the minimum number of additions needed to make the string valid\n        return ans;\n    }\n}\n```\n```ruby []\n# @param {String} s\n# @return {Integer}\ndef min_add_to_make_valid(s)\n  # Initialize the counter for minimum additions needed\n  ans = 0\n  \n  # Initialize the balance of parentheses (open - close)\n  bal = 0\n  \n  # Iterate through each character in the string\n  s.each_char do |ch|\n    if ch == \'(\'\n      # If it\'s an opening parenthesis, increment the balance\n      bal += 1\n    else\n      # If it\'s a closing parenthesis, decrement the balance\n      bal -= 1\n    end\n    \n    # If balance becomes negative (more closing than opening parentheses)\n    if bal < 0\n      # Add the absolute value of balance to answer\n      # This represents the number of opening parentheses we need to add\n      ans += -bal\n      # Reset balance to 0 since we\'ve accounted for the imbalance\n      bal = 0\n    end\n  end\n  \n  # After processing all characters, add any remaining open parentheses\n  # This represents the number of closing parentheses we need to add\n  ans += bal\n  \n  # Return the minimum number of additions needed to make the string valid\n  ans\nend\n```\n```rust []\nimpl Solution {\n    pub fn min_add_to_make_valid(s: String) -> i32 {\n        // Initialize the counter for minimum additions needed\n        let mut ans = 0;\n        \n        // Initialize the balance of parentheses (open - close)\n        let mut bal = 0;\n        \n        // Iterate through each character in the string\n        for ch in s.chars() {\n            if ch == \'(\' {\n                // If it\'s an opening parenthesis, increment the balance\n                bal += 1;\n            } else {\n                // If it\'s a closing parenthesis, decrement the balance\n                bal -= 1;\n            }\n            \n            // If balance becomes negative (more closing than opening parentheses)\n            if bal < 0 {\n                // Add the absolute value of balance to answer\n                // This represents the number of opening parentheses we need to add\n                ans += -bal;\n                // Reset balance to 0 since we\'ve accounted for the imbalance\n                bal = 0;\n            }\n        }\n        \n        // After processing all characters, add any remaining open parentheses\n        // This represents the number of closing parentheses we need to add\n        ans += bal;\n        \n        // Return the minimum number of additions needed to make the string valid\n        ans\n    }\n}\n```\n```swift []\nclass Solution {\n    func minAddToMakeValid(_ s: String) -> Int {\n        // Initialize the counter for minimum additions needed\n        var ans = 0\n        \n        // Initialize the balance of parentheses (open - close)\n        var bal = 0\n\n        // Iterate through each character in the string\n        for ch in s {\n            if ch == "(" {\n                // If it\'s an opening parenthesis, increment the balance\n                bal += 1\n            } else {\n                // If it\'s a closing parenthesis, decrement the balance\n                bal -= 1\n            }\n\n            // If balance becomes negative (more closing than opening parentheses)\n            if bal < 0 {\n                // Add the absolute value of balance to answer\n                // This represents the number of opening parentheses we need to add\n                ans += -bal\n                // Reset balance to 0 since we\'ve accounted for the imbalance\n                bal = 0\n            }\n        }\n\n        // After processing all characters, add any remaining open parentheses\n        // This represents the number of closing parentheses we need to add\n        ans += bal\n\n        // Return the minimum number of additions needed to make the string valid\n        return ans\n    }\n}\n```\n### Complexity (python as example)\n- Time complexity: O(n)\n\n- Space complexity: O(1)\n\n## Explained step by step\n1. We start with a class called `Solution` that has a method `minAddToMakeValid`. This method takes a string `s` as input and returns an integer.\n2. We create a variable `ans` and set it to **0**. This will keep track of how many parentheses we need to add.\n3. We create another variable `bal` and set it to **0**. This will keep track of the balance between opening and closing parentheses.\n4. We then go through each character in the input string `s`:\n- a. If the character is an opening parenthesis \'(\', we increase `bal` by **1**.\n- b. If it\'s a closing parenthesis \')\', we decrease **bal** by **1**.\n5. After each character, we check if `bal` has become negative. If it has:\n-  We add the absolute value of `bal` to ans. This is because a negative balance means we have more closing parentheses than opening ones, so we need to add some opening ones.\n- We then reset `bal` to **0** since we\'ve fixed the imbalance.\n6. After we\'ve gone through all the characters, we add the final value of `bal` to `ans`. This is because if `bal` is positive, it means we have more opening parentheses than closing ones, so we need to add some closing ones.\n7. Finally, we return `ans`, which represents the total number of parentheses we needed to add to make the string valid.\n\nIn essence, this method counts how many parentheses we need to add to make sure every opening parenthesis has a matching closing parenthesis, and vice versa.\n\n![image.png](https://assets.leetcode.com/users/images/410e442d-cd4d-4898-8491-d73274757cac_1728433680.8203661.png)\n\n![image.png](https://assets.leetcode.com/users/images/57926bd5-e4e7-4586-855c-6b561a48182f_1728433656.3987143.png)\n\n\n\n![image.png](https://assets.leetcode.com/users/images/9dc1b265-b175-4bf4-bc6c-4b188cb79220_1728176037.4402142.png)\n\n
['Swift', 'Python', 'C++', 'Java', 'TypeScript', 'Python3', 'Rust', 'Ruby', 'JavaScript', 'C#']