defaang
defaang copied to clipboard
csdojo-defaang
[CONTENT] Solve this problem and write out a solution for it. (or make a video)
Description
One of the approved questions we have was recently asked by Google, and it is this:
You need to check whether the string is well nested or not based on two conditions:
- If they are, return the string as-is.
- If they are not, repair the string so that the parentheses are well nested and return the result.
You can perform three actions to validate the string. Three actions are: Delete, Add, Update.
You must convert it a well-nested string with the minimum number of actions.
Test Examples: Input: (() Output: (()), or () or ()()
Input: (()))) Output: ((()))
It'll be good to have a solution for this so we can display it on the website, and so we can make a video out of it.
The solution should be language-specific like python or is it ok with any language?
it's ok with any language!
if we have solutions in multiple languages, it'd be even cooler I think
@Akshay1018 by the way, the question is much harder when there's the "update" option instead of just delete and add. Any thoughts about it? Should it be phrased in a two-stage way?
@ykdojo Right, this question is hard because we need to return the minimum operations based on two conditions. Let's talk about the conceptual overview. I will take an example and try to return minimum operations. example-1 input - ((()
intuition-1 we can add two parentheses at last and our total operation to make it valid will be 2 right? ( ( ( ) ) ) ^^
intuition-2 Please observe we can replace the second index with closed parentheses and our total operation to make it valid will be only 1. before update operation - ( ( ( ) After the update operation - we are replacing index 1 ( ) ( )
If we take a minimum of both the 2nd intuition will be returned {Math.min(2,1)}
We can approach this using Dynamic programming and we need to take care of edge cases, like when to use the operation to return the minimum. Please add some more thoughts and changes in the conceptual overview then we will come up with the DP solution + complexity tradeoffs.
@Akshay1018 I'll get back to you! I didn't have a chance to respond here yet
try to return minimum operations
Are you saying we need to return an integer from this function? Because if that's the case, the problem would be much easier, and honestly more realistic as an interview question.
we need to take care of edge cases, like when to use the operation to return the minimum.
"when to use the operation to return the minimum"
^Can you clarify what you mean by that exactly?
Other than that:
Please add some more thoughts and changes in the conceptual overview then we will come up with the DP solution + complexity tradeoffs.
This sounds good!
@ykdojo When we get the minimum number of operations to solve this problem then we can easily create the valid parenthesis using backtracking.
From the above example, we know that using only one operation n =1 we can solve the problem. The valid parenthesis we can make is 2n 2 x 1, with two open and two closed parentheses. There are no restrictions on the order, we can return the parenthesis in any order.
minimum operations (n) = 1 valid parenthesis = 2n = 2 x 1 = 2
output = (()) or ()()
is this sounds good?
I can say this is two step process/solution:
Count the operations we need to add to make it valid.
Using that count, create the valid parenthesis and return the result.
Sounds good.
I think we can split it into two problems then, if it's with you.
The first problem will ask you to output the min # operations.
The second one, with the same setup, will ask you to output a list (or a set) of end-state valid parenthesis strings.
Exactly, we can say the second one is follow up output a list (or a set) of end-state valid parenthesis strings.
@Akshay1018 sounds good! I'll start working on solving it, then. Feel free to start writing a solution for it if you'd still like to, as well.
Brute Force Solution:
Step 1 counts a minimum number of operations to make parenthesis valid.
`class Solution { public int minimumOperations(String str){ if(str.length() ==0){ return 0; } int addOperations = 0; int deleteOperations = 0; int replaceOperations = 0; //check if string is well nested then return as-is if(isValidString(str)){ return str; }else{ addOperations += addOperationCount(str); deleteOperations += deleteOperationsCount(str); replaceOperations += replaceOperationsCount(str); } return Math.min(addOperations, Math.min(deleteOperations, replaceOperations)); } // count add operations public int addOperationCount(String str){ Stack<Character> st = new Stack<>(); int count =0;
for(char ch : str.toCharArray()){
if(ch == '('){
st.push(ch);
}else if(ch == ')' && !st.isEmpty()){
st.pop();
count+= 2;
}
}
return str.length() - count;
}
// count delete operations
public int deleteOperationsCount(String str){
int total =0;
int temp =0;
for(char ch: str.toCharArray()){
if(ch == '('){
total += 1;
}else if(ch == ')' && total != 0){
total -= 1;
}else{
temp += 1;
}
}
return total + temp;
}
// count replace operations
public int replaceOperationsCount(String str){
int openParenthesisCount =0;
int closeParenthesisCount =0;
int openReplaceCount =0;
int closeReplaceCount =0;
for(char ch: str.toCharArray()){
if(ch == '('){
openParenthesisCount+= 1;
}
if(ch == ')'){
closeParenthesisCount+= 1;
}
}
if(openParenthesisCount % 2 ==0){
openReplaceCount += Math.abs(openParenthesisCount / 2);
}else{
openReplaceCount += Math.abs(openParenthesisCount / 2 + 1);
}
if(closeParenthesisCount % 2 == 0){
closeReplaceCount += Math.abs(closeParenthesisCount / 2);
}else{
closeReplaceCount += Math.abs(closeParenthesisCount / 2 + 1);
}
return openReplaceCount+closeReplaceCount;
}
// check valid String
public boolean isValidString(String str){
int validCount =0;
for(char ch: str.toCharArray()){
if(ch == '('){
validCount += 1;
}
if(ch == ')'){
validCount -= 1;
}
}
return validCount == 0 ? true : false;
}
}`
Step -2 Generate Valid parenthesis with minimum count and return the result
class Solution { public List<String> generateValidParenthesis(int num){ List<String> res = new ArrayList<>(); backtrack(res, num, 0, 0, ""); return res; } public void backtrack(List<String> res, int max, int close, int open, String curr){ if(res.size() == num*2){ res.add(curr); return; } if(open < max){ backtrack(res, max, open+1, close, curr+"("); } if(close < open){ backtrack(res, max, open, close+1, curr+")"); } } }
@ykdojo Please check this solution. This is a brute force approach, we can optimize this solution, and let me know your thoughts on it. Thanks.
@ykdojo sure, please check on this and we will come up with an optimized solution.
here is my solution the solution , will use 2 stack and 2 counters for each closing case and open case and will flip each close case if no open case for it and add it to open cases stack
full code with test cases checker https://gist.github.com/mamonraab/9d2d537bfc4537fb86219d8a3c70e7be
def correctstring(s):
open_stack = []
close_stack = []
open_counter = 0
close_counter = 0
for ch in s:
if ch == '(':
# open case
open_stack.append(ch)
open_counter +=1
close_counter -=1
elif ch == ')':
#close case
if (len(open_stack) == len(close_stack) ) and (open_counter == 0) and (close_counter == 0):
open_stack.append('(')
open_counter +=1
close_counter -=1
else:
close_stack.append(ch)
close_counter +=1
open_counter -=1
while open_counter < 0:
open_stack.append('(')
open_counter +=1
while close_counter < 0:
close_stack.append(')')
close_counter +=1
return ''.join(open_stack) + ''.join(close_stack)
