Minimum Number of Swaps to Make the String Balanced Weekly + Contest 253 Editorial || Java ✅
\tclass Solution {\n\t\t//    Weekly Contest 253 Solutions\n\n\t\t//    Guyz do mention if you\'ve some better solution approach. Below are the implementation I
\tclass Solution {\n\t\t//    Weekly Contest 253 Solutions\n\n\t\t//    Guyz do mention if you\'ve some better solution approach. Below are the implementation I used during contest\n\n\t\t//    **********************************************************************************\n\t\t//    Que - 1\n\n\t\t// I did the brute force approach. I think solution is self explanatory.\n\t\tpublic boolean isPrefixString(String s, String[] words) {\n\t\t\tStringBuilder strb = new StringBuilder();\n\t\t\tfor(String st : words) {\n\t\t\t\tstrb.append(st);\n\t\t\t\tif(strb.toString().equals(s)) return true;\n\t\t\t}\n\t\t\treturn false;\n\t\t}\n\n\t\t// In each and every iteration we\'ll change the maximum element to x-x/2 where x is the maximum element in current iteration.\n\t\t// For getting maximum element in every iteration we\'ll make use of priority queue    \n\t\t//    **********************************************************************************\n\t\t//    Que-2 Medium\n\t\tpublic int minStoneSum(int[] piles, int k) {\n\t\t\tPriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());\n\t\t\tfor(int val : piles) pq.add(val);\n\t\t\twhile(k-- != 0) {\n\t\t\t\tint x = pq.remove();\n\t\t\t\tpq.add(x-x/2);\n\t\t\t}\n\t\t\tint sum = 0;\n\t\t\twhile(!pq.isEmpty()) {\n\t\t\t\tsum+=pq.remove();\n\t\t\t}\n\t\t\treturn sum;\n\t\t}\n\n\t\t// After removing the balanced part our string comes aut of like (a*[)(b*]). I did some test cases and we can balance string of such types using following number of steps\n\t\t// min steps = (l+2)/4 steps\n\t\t//    **********************************************************************************\n\t\t//    Que-3 Medium\n\t\tpublic int minSwaps(String s) {\n\t\t\tStack<Character> st = new Stack();\n\t\t\tfor(char c : s.toCharArray()) {\n\t\t\t\tif(c == \'[\') st.push(c);\n\t\t\t\telse if(c == \']\') {\n\t\t\t\t\tif(!st.isEmpty() && st.peek() == \'[\') st.pop();\n\t\t\t\t\telse st.push(c);\n\t\t\t\t}\n\t\t\t}\n\t\t\treturn (st.size()+2)/4;\n\t\t}\n\n\t\t// This is a variation of Longest increasing subsequence. At an index i We just need to store the max length of longest increasing subsequence we can create whose last index element will be ith element\n\t\t//    **********************************************************************************\n\t\t//    Que-4\n\t\tpublic static int bs(ArrayList<Integer> list, int val) {\n\t\t\tint start = 0, end = list.size();\n\t\t\twhile (start < end) {\n\t\t\t\tint mid = start + (end-start)/2;\n\t\t\t\tif(list.get(mid) <= val) {\n\t\t\t\t\tstart = mid+1;\n\t\t\t\t} else {\n\t\t\t\t\tend = mid;\n\t\t\t\t}\n\t\t\t}\n\t\t\treturn start;\n\t\t}\n\n\n\t\tpublic int[] longestObstacleCourseAtEachPosition(int[] arr) {\n\t\t\tint n = arr.length;\n\t\t\tint[] res = new int[arr.length];\n\t\t\tArrayList<Integer> list = new ArrayList<>();\n\t\t\tint maxv = 1;\n\t\t\tfor(int i=0; i<n; i++) {\n\t\t\t\tint idx = bs(list, arr[i]);\n\t\t\t\tif(idx == list.size()){\n\t\t\t\t\tlist.add(arr[i]);\n\t\t\t\t}\n\t\t\t\telse {\n\t\t\t\t\tlist.set(idx, arr[i]);\n\t\t\t\t}\n\t\t\t\tres[i] = idx+1;\n\t\t\t}\n\t\t\treturn res;\n\t\t}\n\t\t//    **********************************************************************************\n\t}
[]