[CONTENT] Solve this problem and write out a solution for it. (or make a video)

[ykdojo]

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:

1. If they are, return the string as-is.
2. 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.

[Rakteem007]

can you assign this to me?

[Akshay1018]

The solution should be language-specific like python or is it ok with any language?

[ykdojo]

it's ok with any language!

if we have solutions in multiple languages, it'd be even cooler I think

[Rakteem007]

@ykdojo sir , I fixed the issue

[ykdojo]

@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?

[Akshay1018]

@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]

@ykdojo any thoughts on this?

[ykdojo]

@Akshay1018 I'll get back to you! I didn't have a chance to respond here yet

[Akshay1018]

@ykdojo cool! Take your time. Thanks.

[ykdojo]

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!