Good morning. Hope you are doing well and keeping safe. Not sure what is happening with the COVID-19 pandemic. In some parts of the world i.e., Peru, hospitals are full and people are dying out of control. On the other hand in Sicily, Italy most people are socializing and not wearing masks. In Israel the entire population is receiving the second shot of the COVID-19 vaccine.
Close to home, my wife and I continue to practice social distancing. On Sunday we had family members visiting. No one wore masks but we all kept at a distance from each other. Of course, we will not know if something happened for a couple weeks.
Yesterday evening I took a look at LeetCode 1249. Minimum Remove to Make Valid Parentheses. I did not have time to come up with a solution. This morning I started a little earlier so I could allot some time to finishing and posting my solution.
Given a string s of '(' , ')' and lowercase English characters.
Your task is to remove the minimum number of parentheses ( '(' or ')',
in any positions ) so that the resulting parentheses string is valid
and return any valid string.
Formally, a parentheses string is valid if and only if:
o It is the empty string, contains only lowercase characters, or
o It can be written as AB (A concatenated with B), where A and B are valid strings, or
o It can be written as (A), where A is a valid string.
Constraints:
o 1 <= s.length <= 10^5
o s[i] is one of '(' , ')' and lowercase English letters.
The problem is similar to the one in which we are asked to check if a set of parenthesis is valid or not. In this one we need to remove the minimum possible number of parenthesis to return a balanced string. It is somewhat more complicated than the similar one.
LeetCode does a good job with the requirements. They complement it with four examples.
I will solve this problem from home using a Windows 10 computer, the VSCode IDE and the Java programming language. For that reason I will need to build some test code (scaffolding) to read in the input string, pass it to the required function / method and display the results. Please note that this test code IS NOT PART OF THE SOLUTION.
When I am ready to test at LeetCode I will copy and paste the contents of my function / method and check if it passes the initial tests and then if it is accepted.
public String minRemoveToMakeValid(String s) {
}
The signature of the function / method is as expected. Not much to add.
lee(t(c)o)de) main <<< s ==>lee(t(c)o)de)<== main <<< output ==>lee(t(c)o)de<== a)b(c)d main <<< s ==>a)b(c)d<== main <<< output ==>ab(c)d<== ))(( main <<< s ==>))((<== main <<< output ==><== (a(b(c)d) main <<< s ==>(a(b(c)d)<== main <<< output ==>a(b(c)d)<==
Our test code needs to read the input string. We display the string to make sure all is well so far. We must be making a call to the method / function of interest and displaying the result. It seems that our four tests return the expected results.
/**
* Test scaffolding
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read input string ****
String s = br.readLine().trim();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< s ==>" + s + "<==");
// **** call method of interest and display output ****
System.out.println("main <<< output ==>" + minRemoveToMakeValid(s) + "<==");
}
Our test scaffolding uses a buffered reader to read in the string. The test code displays the string. The function / method of interest is called and the returned string is displayed. Not much to add here either.
/**
* Method of interest.
* o No close parenthesis before open parenthesis.
* o Open and close parentesis must balance (+1 and -1).
* Runtime complexity: O(n)
*
* Runtime: 8 ms, faster than 97.33% of Java online submissions.
* Memory Usage: 40 MB, less than 39.11% of Java online submissions.
*/
static String minRemoveToMakeValid(String s) {
// **** sanity check(s) ****
if (s == null)
return null;
if (s.equals(""))
return "";
// **** initialization ****
StringBuilder out = new StringBuilder();
int pc = 0;
char[] chArr = s.toCharArray();
// **** traverse string right to left <- ****
for (int i = chArr.length - 1; i >= 0; i--) {
// **** for ease of use ****
char ch = chArr[i];
// **** count parenthesis ****
if (ch == ')')
pc++;
else if (ch == '(') {
// **** update count or remove parenthesis ****
if (pc == 0) {
// **** remove this parenthesis ****
chArr[i] = 'X';
} else {
// **** count this parenthesis ****
pc--;
}
}
}
// **** check if parenthesis are NOT balanced ****
if (pc != 0) {
// **** no parenthesis counted yet ****
pc = 0;
// **** traverse string left to right -> ****
for (int i = 0; i < chArr.length; i++) {
// **** for ease of use ****
char ch = chArr[i];
// **** count parenthesis ****
if (ch == '(')
pc++;
else if (ch == ')') {
// **** update count OR remove parenthesis ****
if (pc == 0) {
// **** remove this parenthesis ****
chArr[i] = 'X';
} else {
// **** count this parenthesis ****
pc--;
}
}
}
}
// **** build string to return ****
for (char ch : chArr) {
if (ch != 'X')
out.append(ch);
}
// **** return output string ****
return out.toString();
}
We perform some sanity checks. I always like to check the arguments to make sure they are what we expect them to be.
We will use a string builder to build the string that we need to return. We could have used a String but it is considerably more efficient to use a string builder. If interested in verifying this last statement, please swap the use of the string builder with strings and compare the run times.
The pc variable (parenthesis count) is used to determine if parenthesis are balanced. For each open parenthesis we must have a closing one. In our case we will increment the pc variable when we encounter an open parenthesis and decrement it when we see a close parenthesis.
The chArr[] is used for simplicity. We could extract a character from the string each time we needed one, or just initialize and populate a character array. We will also be altering the character arrays so if we use strings the performance hit will be higher.
We will be traversing the string from right to left and if needed form left to right. The reason is to take care of unbalanced open and closed parenthesis.
We enter the first loop and process each character in the chArr[] at a time. If the character is a close parenthesis we just update the counter. If the character is a open parenthesis we check if there is no previous parenthesis. This will take care of ending parenthesis. We flag the condition in the chArr[] because we need to remove this parenthesis from the returning string. If that is not the case, we just count the parenthesis and continue looping.
Note that I started moving right to left on the string. In the initial code I had the second loop before this one. I was looking to see if I could make the code more efficient by making changes in how the string builder was being populated. You can swap the loops and all should work the same.
If all parentheses are balanced, there is no need to enter the second loop.
If the parentheses are not balanced, then we need to traverse the string (character array) in reverse order to remove unneeded unbalanced parenthesis. The only difference is checking for an open or a close parenthesis first.
After we pass the two loops, we need to build a string to return. For that we use the string builder. We append all remaining parenthesis and all lower case letters. Note that we had any unbalanced parenthesis replaced by ‘X’.
We return the string representation of the string builder as the answer.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset.
One last thing, many thanks to all 5,959 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.
Regards;
John
john.canessa@gmail.com