⌘ [Java] 4 Solutions | Intuition | O(n) | O(1) Solutions
Every-time I come across a parenthesis problem, I see stack involved in it. Now, it might not always be the case but mostly we could solve them using stack. One
Every-time I come across a parenthesis problem, I see stack involved in it. Now, it might not always be the case but mostly we could solve them using stack. One note to consider, stack might not always be the optimal solution to these parenthesis problem. ( We can for sure reduce our space if we are given some input constraint in terms of number of valid chars to 2 , for eg : in this question we are given that `s[i] can either be [ or ] `). Another such problems : \n* [Score of parenthesis](https://leetcode.com/problems/score-of-parentheses/)\n* [Longest Valid Parenthesis](https://leetcode.com/problems/longest-valid-parentheses/)\n\nThe following 4 solutions are some-what close to each other. ( just some slight variations )\n* 2 solutions with TC : `O(n)`\n* 2 solutions with TC : `O(1)`\n\n# \u2714\uFE0F Solution 1 : Using stack\n* We are given a parenthesis string where `# of \'[\' == # of \']\'`.\n* We need to find the min number of swaps to make it balanced.\n* The string might contain some `balanced sub-portions` which will not be involved in making swaps. As, the sub-portion is already balanced and we need to minimize the # of swaps, thus, the `balanced sub-portions` are not useful to us.\n\n\n\uD83D\uDCCE Algorithm : \n\n* Take a sample input : "`] ] [ [ ] [ [ ]`"\n* Remove the balanced sub-portions from the given string using stack.\n* We are left with a string of following format :\n\t*  `] [`\n\t*  `] ] ] [ [ [`\n\t*  see the pattern ?\n\t*  `# of closing parenthesis` followed by `# of opening parenthesis`\n* The stack contains only the unbalanced string now. ( `of even length` )\n* Take some smaller cases and see the pattern : \n\t* `] [` : need 1 swap\n\t* `] ] [ [` : need 1 swap to be made of `0th` and `3rd` index.\n\t* `] ] ] [ [ [` : need 2 swap to be made\n\t\t* `1st` swap between `0th` and `5th` index. The string becomes : `[ ] ] [ [ ]`\n\t\t* `2nd` swap between `2nd` and `3rd` index.\n\n\uD83D\uDCCE Observations : \n* Observation 1: If we are left with a string of length `n` in stack then, `# of swaps needed:`\n\t* `n=2` : `1` swap\n\t* `n=4` : `1` swap\n\t* `n=6` : `2` swap\n\t* `n=8` : `2` swap\n\t* `n=10` : `3` swap\n\t* and so on.\n\n# \u2714\uFE0F Code : Using Stack : \n```\nclass Solution {\n    public int minSwaps(String s) {\n        // remove the balanced part from the given string\n        Stack<Character> stack = new Stack<>();\n        for(char ch : s.toCharArray()) {\n            if(ch == \'[\')\n                stack.push(ch);\n            else {\n                if(!stack.isEmpty() && stack.peek() == \'[\')\n                    stack.pop();\n                else\n                    stack.push(ch);\n            }\n        }\n        int unb = stack.size()/2; // # of open or close bracket\n        return (unb+1)/2;\n    }\n}\n```\n\n\n\uD83D\uDCCE Result : \n![image](https://assets.leetcode.com/users/images/e331e969-5d00-4ece-9864-1f2d2865d52c_1641657967.9818897.png)\n\n\uD83D\uDCCE Complexity Analysis : \n* TC : `O(n)`\n* SC : `O(n)`\n\n****\n\n# \u2714\uFE0F Solution 2 : Using Stack and Simulation : \n Observations :\n\n* If after removing balanced portions, we are left with a string of length `n` then, after 1 swap we are left with an unbalanced string of length `n-4` because `2` pairs got balanced. \n\t* eg: `n=6` i.e. "`] ] ] [ [ [`"\n\t\t* `1st swap : ` swap(0, 5) -> "` [ ] ] [ [ ] `" ( 2 pairs got created and unbalanced string has length`n-4` )\n\t\t* We need to keep swaping until this `n` becomes `neg`. i.e. no parenthesis is left for swapping.\n```\nclass Solution {\n    public int minSwaps(String s) {\n        // remove the balanced part from the given string\n        Stack<Character> stack = new Stack<>();\n        for(char ch : s.toCharArray()) {\n            if(ch == \'[\')\n                stack.push(ch);\n            else {\n                if(!stack.isEmpty() && stack.peek() == \'[\')\n                    stack.pop();\n                else\n                    stack.push(ch);\n            }\n        }\n        \n        int n = stack.size();\n        int swap = 0;\n        while(n > 0) {\n            swap++;\n            n-=4;\n        }\n        return swap;\n    }\n}\n```\n\n\uD83D\uDCCE Result : \n![image](https://assets.leetcode.com/users/images/bcb3eb84-d8ca-4221-a00e-5ad7d48470cc_1641660801.9880626.png)\n\n\n\uD83D\uDCCE Complexity Analysis : \n* TC : `O(n)`\n* SC : `O(n)`\n\n****\n\n# \u2714\uFE0F Solution 3-4 : Using Constant Space :\n* TC : `O(n)`\n* SC : `O(1)`\n\nAs I mentioned above, using stack might not always be the optimal solution to the parenthesis problems. \n* We are using stack to retain the unbalanced portions of the string. Or we can say, to get the number of open and close parenthesis that are out of order and needs swapping. Is it possible to find this number without using a stack ?\n* Remember earlier, after removing balanced sub-portions the `stack size = open brackets + close brackets`.\n\n\uD83D\uDCCE Observations : \n* As we only have two chars in our input string ( `[` & `]` ), we can use two variables.\n\n\n**\u2714\uFE0F Code 1 w/ comments :** \n```\nclass Solution {\n    public int minSwaps(String s) {\n        int open = 0, unbalanced = 0;\n        for(char ch : s.toCharArray()) {\n            if(ch == \'[\')\n                open++;\n            else {\n                // check if we have found an open bracket before\n                if(open > 0) {\n                    // we have a proper pair\n                    open--; // we used one open bracket for this pair\n                } \n                else unbalanced++;\n            }\n        }\n        // add the remaining open bracket which are left out for a pair\n        unbalanced += open;\n        unbalanced /= 2; // # of open brackets or # of close brackets\n        return (unbalanced+1)/2;\n    }\n}\n```\n\uD83D\uDCCE  Result : \n![image](https://assets.leetcode.com/users/images/0b3483d1-e41e-4c7a-a788-5b87e5e1a4db_1641666116.80611.png)\n\n\n**\u2714\uFE0F Code 2 w/ comments :** [ `More Intuitive`]\n```\nclass Solution {\n    public int minSwaps(String s) {\n        int open = 0, close = 0, unbalanced = 0;\n        for(char ch : s.toCharArray()) {\n            if(ch == \'[\') open++;\n            else {\n                if(open > close) // i.e we have an extra open [ to be used in a pair\n                    close++;\n                else unbalanced++;\n            }\n        }\n        return (unbalanced+1)/2;\n    }\n}\n```\n\uD83D\uDCCE Results:\n![image](https://assets.leetcode.com/users/images/0c7e9bb7-aa3d-4d76-ba0d-4ac4e0c8acc5_1641666449.1896808.png)\n\n****
['Stack', 'Java']