Blog

Leetcode 1963: Minimum Number of Swaps to Make the String Balanced

Oct 6, 2024

About

This leetcode problem is basically us to find the minimum number of swap operations are needed to make a string of ”[]” symbols balanced. Balanced being if each opening ”["" symbol also has a closing ”]” symbol. For example, the following would be examples of balanced strings.

1. []
2. [[]]
3. [][][]

Thoughts

One thing to notice off the bat is when considering certain testcases, it is already possible that a string already contains a balanced string. For example, testcase ]][][[ already has a balanced string in the middle, so it is the same as ]][[. For example, all testcases either eventually become testcases such as ][, ]][[, ]]][[[ ect.

After we see this, it is now about finding a remainder inside our testcase string of extra unmatched chars. For example, in ][ the remained would be one, which can be viewed either as having one unmatched opening char, or one unmatched closed char.

After drawing out these certain testcases, I saw a certain pattern involving the remaining total of unmatched charecters in the sring.

1. ][ = 1 Swaps needed
2. ]][[ = 1 Swaps needed
3. ]]][[[ = 2 Swaps needed
4. ]]]][[[[ = 2 Swaps needed
5. ]]]]][[[[[ = 3 Swaps needed

The pattern being, that for the remaining amount of unmatched symbols at the end of the string is then Math Ceil (remaining amount of unmatched chars / 2) is the number of swaps needed.

Implementation

There are two ways you can solve this problem. One way is to use a stack data structure to keep track of previous symbols, and then pushing and popping accordingly. However, what I ended up doing to save memory usage was to simulate the stack size instead. Since we only need to return the minimal amount of swaps needed, we don’t need to have a stack, only the state of the would be stack’s size / length. Once I for loop to simulate the stack size, I simply just return the Math.ceil(remainder / 2) to return the minimal amount of swaps needed.

Leetcode 2696: Minimum String Length After Removing Substrings

Dec 31, 1999

About

This problem is basically asking after you replace every occurrence of a substring “AB” or “CD” in your testcase string, return the length of the new string. For example:

1. “ABCDZ” => “Z” => return 1;
2. “QABABABQ” => “QQ” => return 2;
3. “ACDB” => "" return 0;

Thoughts

The first two example testcases are pretty straight forward. Just remove “AB” substrings, then remove all “CD” substrings. However, the third testcase gets interesting where we remove “AB”, then remove “CD”. However, after removing the “CD” we are left with “AB”, which can then be removed again to return a blank string "" / a return string length of 0. After seeing this I immediately just wanted to use regular expressions, as that would be perfect for finding substrings present in my main string, as well as for preforming replaceAll operations to remove “AB” and “CD” substrings from the main testcase string.

Implementation

I simply just made a while loop that only ends once my given String s no longer has a “AB” or a “CD” substring present inside of itself. This is done by using the regular expression /AB|CD/, which just checks for any occurrence of an “AB” or “CD”. The .test(s) then just takes my regular expressions, searches the string using said regular expression, then returns true or false.

Inside my while loop, I then use s.repalceAll and /AB|CD/g to replace all occurrences of ABs and CDs from my current string. The regular expression is pretty similar to the top, I just use G to make sure its global since it’s a replace all.

Lastly, once my String S no longer has any occurrences of substrings “AB” or “CD”, I exit my while loop and then just return the length of my now AB and CD substring freed string.

Leetcode 3011: Find if Array Can Be Sorted

Dec 31, 1999

About

There are two main parts to this problem. First, we need to be able to preform a sort on the array of values. Second, we must evaluate whether two elements in the array need to be swapped, and whether they are swappable given their count of on (1) in their binary representation of themselves. If the given array is already sorted, we can return true. If the given array is unsorted, then we must return whether it can become sorted by swapping elements when their bit counts are equal to each other. Returning false means that we have reached a point where the array is unsorted, and elements are different bit counts from each other, meaning it’s impossible to complete the swap operation.

For example:

1. [1,5,2] = false, 5 and 2 can’t be swapped, even though they need to be swapped
2. [1,2,3,4,5] = true, sure some numbers can’t be swapped, but since its already sorted we don’t need to worry

Thoughts

Since this is a bitwise problem, a while loop can find the number of on (1) bits a number has. Also, an ideal sorting algorithm to use would be bubble sort, since the problem specifies you are preforming swaps between elements. Since the main idea is to test for bit counts and whether elements in the array are less than each other, bubble sort is the first thing that popped into my head. With bubble sort, I could check how elements values differ from each other, as well as how their bit counts differ from each other.

Implementation

For my solution I went with a bubble sort approach, since bubble sort is well known for being a sort algorithm that preforms a bunch of swaps between a left and right pointer. By using a bubble sort to implement a solution, I could also include a check during swaps to check if the two elements I’m swapping at the time are different bit counts. If at any point they are different bit counts and need to be swapped, I can simply exit early and return false. Otherwise, I continue on with my business until the array is fully sorted and return true.

For finding the bit count of on (1) bits of a number, I simply use a while loop that counts the & of each first bit. Then to iterate down, I just do an arithmetic shift right, >> 1, to effectively half and floor the number each iteration until the number I am checking reaches zero.

Closing Thoughts

After rereading the question, I noticed that leetcode did specify that only two ADJACENT elements can be swapped in one operation. While my solution passes all test cases, my solution does technically break the only ADJACENT elements rule. https://www.geeksforgeeks.org/bubble-sort-algorithms-by-using-javascript/ The bubble sort algorithm template on geeksforgeeks actually follows this rule a bit better, but at the end of the day still gets the job done :p

Newer posts