The parenthesis template Question || Brute intuitive || interview
Get to solve the best parenthesis question in brute and optimised way\n\nunderstanding problem solving\n\n\n1541. Minimum Insertions to Balance a Parentheses St
Get to solve the best parenthesis question in brute and optimised way\n\nunderstanding problem solving\n\n\n[1541. Minimum Insertions to Balance a Parentheses String](https://leetcode.com/problems/minimum-insertions-to-balance-a-parentheses-string/solutions/5348641/the-parenthesis-template-question-brute-intuitive-interview/)\n[921. Minimum Add to Make Parentheses Valid](https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/solutions/5348632/brute-intuitive-solution-with-and-without-stack-beast-time-and-space/)\n[20. Valid Parentheses](https://leetcode.com/problems/valid-parentheses/solutions/5159895/brute-intuitive-solution-beats-98/) --> *simple yet tricky*\n[301. Remove Invalid Parentheses](https://leetcode.com/problems/remove-invalid-parentheses/solutions/5305306/have-fun-solving-this-easy-problem/) -> **Important**\n[32. Longest Valid Parentheses](https://leetcode.com/problems/longest-valid-parentheses/solutions/5348623/simple-solution-in-java-must-read/)\n[1614. Maximum Nesting Depth of the Parentheses](https://leetcode.com/problems/maximum-nesting-depth-of-the-parentheses/solutions/5304994/the-parenthesis-problems/)\n[282. Expression Add Operators](https://leetcode.com/problems/expression-add-operators/solutions/5348619/brute-intuitive-recursive-solution-must-read/) --> **Important**\n[2232. Minimize Result by Adding Parentheses to Expression](https://leetcode.com/problems/minimize-result-by-adding-parentheses-to-expression/solutions/5304516/beats-98/)\n[241. Different Ways to Add Parentheses](https://leetcode.com/problems/different-ways-to-add-parentheses/solutions/5304322/java-simple-solution/)\n[856. Score of Parentheses](https://leetcode.com/problems/score-of-parentheses/solutions/5203496/scoreofparentheses/) --> **unique**\n[678. Valid Parenthesis String]()\n[1003. Check If Word Is Valid After Substitutions]()\n[1963. Minimum Number of Swaps to Make the String Balanced]()\n\n# Code\n```\nclass Solution {\n    public String minRemoveToMakeValid(String s) {\n        int openCount = 0, closeCount = 0;\n        StringBuilder stringBuilder = new StringBuilder();\n\n        // First pass: remove excess closing parentheses\n        for (char c : s.toCharArray()) {\n            if (c == \'(\') {\n                openCount++;\n                stringBuilder.append(c);\n            } else if (c == \')\') {\n                if (openCount > closeCount) {\n                    closeCount++;\n                    stringBuilder.append(c);\n                }\n            } else {\n                stringBuilder.append(c);\n            }\n        }\n\n        // If the counts are balanced, return the result directly\n        if (openCount == closeCount) {\n            return stringBuilder.toString();\n        }\n\n        StringBuilder result = new StringBuilder();\n        openCount = 0;\n        closeCount = 0;\n\n        // Second pass: remove excess opening parentheses from the end\n        for (int i = stringBuilder.length() - 1; i >= 0; i--) {\n            char currentChar = stringBuilder.charAt(i);\n            if (currentChar == \'(\') {\n                if (openCount < closeCount) {\n                    result.append(currentChar);\n                    openCount++;\n                }\n            } else if (currentChar == \')\') {\n                closeCount++;\n                result.append(currentChar);\n            } else {\n                result.append(currentChar);\n            }\n        }\n\n        return result.reverse().toString();\n    }\n}\n\n```\n\n\n## -----------------------------------------------\n\n\ninitially I came up with seperate count for \'*\' and if the count if \'*\' is greater than the difference in count of open and close bracket the return true, but this passed 55 test cases , but that let to the intuitiion of below solution!!\n\nDry run yourself if will make a better understanding for these probelms\n\n\n\n\n# Code\n```\nclass Solution {\n    public boolean checkValidString(String s) {\n        int cmin = 0, cmax = 0; // open parentheses count in range [cmin, cmax]\n        for (char c : s.toCharArray()) {\n            if (c == \'(\') {\n                cmax++;\n                cmin++;\n            } else if (c == \')\') {\n                cmax--;\n                cmin--;\n            } else if (c == \'*\') {\n                cmax++; // if `*` become `(` then openCount++\n                cmin--; // if `*` become `)` then openCount--\n                // if `*` become `` then nothing happens\n                // So openCount will be in new range [cmin-1, cmax+1]\n            }\n            if (cmax < 0) return false; // Currently, don\'t have enough open parentheses to match close parentheses-> Invalid\n                                        // For example: ())(\n            cmin = Math.max(cmin, 0);   // It\'s invalid if open parentheses count < 0 that\'s why cmin can\'t be negative\n        }\n        return cmin == 0; // Return true if can found `openCount == 0` in range [cmin, cmax]\n    }\n}\n```
['Java']