When you go into the software engineering world, the most important thing is problem-solving skills. Why? because if you do not have this skill, no matter how much programming language you expert, you will have obstacles when you face a problem that needs logical treatment, because, in real-world software engineering you do not just retrieve data from API and store it to the view, you also have to filter it, counting it, so on and so forth.

And now we already understand that we have to know to problem-solve, so what? Yes of course to increase that skill we have to routinely practice problem-solving questions like Leetcode. alright without too much chit chat let's jump into the question

Question

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 returns any valid string.

Formally, a parentheses string is valid if and only if:

• It is the empty string, that contains only lowercase characters, or

• It can be written as AB (A concatenated with B), where A and B are valid strings, or

• It can be written as (A), where A is a valid string.

Example 1:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

Example 2:

Input: s = "a)b(c)d"
Output: "ab(c)d"

Example 3:

Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.

Test case

The questions give 3 test cases, before we jump out to the coding, we have to understand the question and solve it using a logical way before jumping out to the code. Alright, let's start with example 1.

1. Test case one

If we see the string give, first things first we have to try to solve things first before we go to the other test case, maybe you wonder why we do not try to solve all of the test cases in one execution. Yes we do not do that because what I want to teach you is to make your brain muscle for problem-solving increase step by step rather than memorizing the pattern

lee(t(c)o)de)

If we notice the pattern of the "(" and ")" we can focus on counting how much the "(" and how much the ")" and then we compare it and make a pair of it.

2. Test case two

a)b(c)d

If we notice this string is given we find ")" first "(", that's mean before we pair the parentheses we need no confirm did the index of ")" is come first before we find "(".

3. Test case three

))((

This case is similar to test case two, but in this thing, we have to remind that "(" also has to remove because there is pair for it, in this case, we will return an empty string.

Solution

Alright, we already break down every test case. Now it's time to work on the solution.

Based on the test case we can do the logic like this

1. Convert the string to the array, because we want to iterate it and implement stack logic

2. We create an empty array to store the final string

3. Okay now we doing for loop, For each index we will confirm like this :

   • If the element is "(" then we store it in the array

   • If the element is ")" and the empty string already fill (not empty anymore) that is means we already have the pair for it then we pop the last element inside the array because we want to make the pair then each parenthesis should have pairing

   • If the element is ")" and the string empty then we set the current element is as an empty string, this is to anticipate the test case three

4. After we do the for loop we have to check that there are parentheses in the stack array when we have to set it to the empty string.

5. Now we already get the valid array, we have to convert it to a string.

Don't worry if you do not understand yet, here is the code you can learn:

const inputString = "lee(t(c)o)de)"

const minRemoveToMakeValid = function(s) {
    const res = s.split('');
    const stack = [];

    for (let i = 0; i < res.length; i++) {
        if (res[i] === '(') {
            stack.push(i);
        } else if (res[i] === ')' && stack.length) {
            stack.pop();
        } else if (res[i] === ')') {
            res[i] = ''
        }
    }

    while (stack.length) {
        const curIdx = stack.pop();
        res[curIdx] = '';
    }

    return res.join('');
};

console.log(minRemoveToMakeValid(inputString))

Conclusion

1. This question can be figured out using stack logic.

2. Before you jump out to the final solution, it will be better if you try to solve every test case first to make your understanding solid.

3. Never give up, the first step is always hard.