Parentheses algorithm pattern

Valid parentheses

https://leetcode.com/problems/valid-parentheses/description/

What if the input is built of a single type of parenthesis?

For example (((((()))))) . In this type of problem, we can simply take the following approach.

1. Initialize left=0
2. Scan the input string from left to right.
3. If ( is found then an increment left++
4. If ) is found and left==0 , it means no matching for the closing bracket, it means the expression is invalid.
5. Else simply decrement left-- to remove the count for the matched bracket.
6. At the end return left == 0

What if the input is built of a multiple type of parenthesis?

In the case of multiple types of parenthesis, if we encounter say ], we don’t know if there is a corresponding opening [ available or not. For example [{]} , since the order of parenthesis does matter therefore on finding ] we can’t say that it is right to decrement counter for ] . Therefore counting approach breaks here.

Approach : Use stack to track the order

1. Initialize a stack S.
2. If we encounter an opening bracket, we simply push it onto the stack.
3. If we encounter a closing bracket, then we check the element on top of the stack. If the element at the top of the stack is an opening bracket of the same type, then we pop it off the stack and continue processing.
4. Otherwise, this implies an invalid expression.
5. In the end, if we are left with a stack still having elements, then this implies an invalid expression.

Following is the code to implement this algorithm.

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
    const stack = [];
    const map = new Map([
        [')', '('],
        ['}', '{'],
        [']', '[']]);
    for (const chr of s) {
        // If closing bracket
        if (map.has(chr)) {
            // closing bracket, top must be corresponding open bracket
            const top = stack[stack.length - 1];
            // if top is not corresponding opening bracket then not a valid pattern
            if (top !== map.get(chr)) {
                return false;
            }
            // since valid so simply remove opening bracket from stack
            stack.pop();
        } else {
            // opening bracket, add into stack
            stack.push(chr);
        }
    }
    // if stack is not empty then invalid pattern
    return stack.length === 0;
};

Generate all combinations of well-formed parenthesis

https://leetcode.com/problems/generate-parentheses/

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Approach 1: Recursion with backtracking

1. Since we need to generate expression using only one type of parenthesis, we can use a counter approach to verify the well-forms of expression.
2. We can use left_counter and right_counter to track the count of open and closed parenthesis used so far.
3. Once the size of the output becomes 2*n and left_counter==right_counter then we reached a valid answer so we can include it.
4. We have two choices

a. Add opening bracket: To generate the future expression if left_counter<n then we can add an opening bracket and increment left_counter

b. Closing bracket: We can’t blindly add a closing bracket as it may make the expression invalid. We can only add if left_counter > right_counter .

Following is the code to implement it.

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
    const ans = [];
    const recursion = (leftCount, rightCount, result) => {
        // base case: handle 
        if (result.length === 2 * n) {
            // if it is valid then add into answer
            if (leftCount === rightCount) {
                ans.push(result.join(''));
            }
            return;
        }
        // Choice 1: choose left
        if (leftCount < n) {
            result.push('(');
            recursion(leftCount + 1, rightCount, result);
            result.pop(); // back track
        }
        // Choice 2: choose right
        if (leftCount > rightCount) {
            result.push(')');
            recursion(leftCount, rightCount + 1, result);
            result.pop(); // back track
        }
    }
    recursion(0, 0, [])
    return ans;
};

Time complexity: Based on Catalan number, time complexity would be O(4^n/(sqrt n))

32. Longest Valid Parentheses substring

https://leetcode.com/problems/longest-valid-parentheses/description/

Given a string containing just the characters ‘(‘ and ‘)’, return the length of the longest valid (well-formed) parentheses substring.

For given input )()()) the longest valid parenthesis substring is ()() i.e. 4 .

Approach 1: Bruteforce i.e. for all possible substring find the len of valid expression

Approach 2: Using a stack

1. As we know, we can use stack to validate the form of expression. We can leverage it here.
2. So far we have used stack to only validate the expression. Here we also need to find out the length of the valid expression.
3. To track the length, we need to push the index of ( instead of the character itself.
4. We can start by pushing -1 to stack.
5. On finding ) , we will pop the top ( from the stack and calculate the local answer by the distance from the top of the stack.
6. If the stack becomes empty then add the current index. This is needed as we need to find out the valid substring.
7. Also, keep updating global ans.

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function (s) {
    let ans = 0;
    const n = s.length;
    const stack = [-1];
    for (let i = 0; i < n; i++) {
        const chr = s[i];
        if (chr === '(') {
            stack.push(i);
        } else {
            stack.pop();
            // reinitialize stack if it become empty to consider substring
            if (stack.length === 0) {
                stack.push(i);
            } else {
                const local = i - stack[stack.length - 1];
                ans = Math.max(ans, local);
            }
        }
    }
    return ans;
};

Approach 3: Using a sliding window two times

1. Since input only has one type of parentheses therefore we can use a counter mechanism to validate the form of expression.
2. We can maintain left and right counter to count the corresponding parenthesis. We can’t use a single counter variable as here we need to find out the length.
3. If left == right it means we have a valid form so update the global answer as left + right.
4. If left < right then it means the form is no longer valid, so we need to reset the window till the latest index.
5. (() In this example, on the ending loop, we will have left=2 and right=1 . Therefore answer will never be calculated.
6. To handle this type of expression, we need to perform the same sliding window from right to left.
7. I.e. we do run the sliding window twice.

const usingSlidingWindowLeftToRight = s => {
    let ans = 0;
    const n = s.length;
    let left = 0;
    let right = 0;
    for (let end = 0; end < n; end++) {
        const chr = s[end];
        if (chr === '(') {
            left++;
        } else {
            right++;
        }

        // In case of violation
        if (right > left) {
            // shrink window
            left = 0;
            right = 0;
        }
        // Ans area
        if (left === right) {
            ans = Math.max(ans, left + right);
        }
    }

    return ans;
}

const usingSlidingWindowRightToLeft = s => {
    let ans = 0;
    const n = s.length;
    let left = 0;
    let right = 0;
    for (let end = n - 1; end >= 0; end--) {
        const chr = s[end];
        if (chr === '(') {
            left++;
        } else {
            right++;
        }
        console.log({ left, right })

        // In case of violation
        if (right < left) { // This condition is changed from right to left
            // shrink window
            left = 0;
            right = 0;
        }
        // Ans area
        if (left === right) {
            ans = Math.max(ans, left + right);
        }
    }
    return ans;
}
/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function (s) {
    return Math.max(usingSlidingWindowLeftToRight(s), usingSlidingWindowRightToLeft(s));
};

301. Remove Invalid Parentheses

https://leetcode.com/problems/remove-invalid-parentheses/description/

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.

Return a list of unique strings that are valid with the minimum number of removals. You may return the answer in any order.

Example 1:

Input: s = "()())()"
Output: ["(())()","()()()"]

Approach: BFS level order traversal

1. For x chars removal if the leftover string is a valid expression then add all the valid expressions after removal of all possible x chars.
2. We need to first find out the minimum value of x
3. We can represent a given string s as the root node.
4. For the graph node which represents string, we can find out all of its neighbors by removing 1 to n-1 chars.
5. During BFS level order traversal, check if the processing node is a valid expression.
6. If valid then all the answer strings will live on the same level.
7. Collect all the answers on the same level.
8. Return the answer at the end of that level i.e. no need to do further traversal.

const isValid = s => {
    let counter = 0;
    for (const chr of s) {
        if(chr === '(') {
            counter++;
        }
        if(chr === ')') {
            counter--;
        }
        if(counter < 0 ) {
            return false;
        }
    }
    return counter === 0;
}
const getNeighbors = (s) => {
    const neighbors = [];
    for (let i=0; i < s.length; i++) {
        const option = s.substring(0,i) + s.substring(i+1);
        neighbors.push(option);
    }
    return neighbors;
}

/**
 * @param {string} s
 * @return {string[]}
 */
var removeInvalidParentheses = function(s) {
    const queue = [s];
    const ans = [];
    const visited = new Map();
    while(queue.length > 0) {
        const n = queue.length;
        let found = false;        
        for (let i=0; i < n; i++) { // level order traversal
            const node = queue.shift();
            const valid = isValid(node);
            // if valid node then add 
            if(valid) {
                found = true;
                ans.push(node);
            }
            
            const neighbors = getNeighbors(node);
            for (const neighbor of neighbors) {
                // Add into stack if not yet visited
                if(!visited.has(neighbor)) {
                    queue.push(neighbor);
                    
                    // mark as visited
                    visited.set(neighbor, true);
                }
            }            
        } 
        // if found then return 
        if(found) {
            return ans;
        }
    }
    return ans;
};

1249. Minimum Remove to Make Valid Parentheses

https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/description/

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:

• It is the empty string, 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.

Approach

We can take the following approach.

1. Need to find out the position of index parentheses in the original string.
2. We can find out using the stack approach as we can store the index in the stack.
3. In case of ( we will add the index to the stack.
4. In case of ) , check the stack top, if it is ( then pop it.
5. If not then add ) into the stack as well to track the invalid parentheses.
6. At the end, the stack will have a position of invalid parentheses.
7. As a second pass, remove these indexes from a string.

/**
 * @param {string} s
 * @return {string}
 */
var minRemoveToMakeValid = function(s) {
    // Phase 1: Find the index of invalid parentheses
    const stack = [];
    for (let i=0; i < s.length; i++) {
        const chr = s[i];
        if(chr === '(') {
            stack.push(i);
        }
        if(chr === ')') {
            if(s[stack[stack.length - 1]] === '(') {
                stack.pop();
            } else {
                stack.push(i);
            }
        }
    }
    if(stack.length === 0) {
        return s;
    }
    // Phase 2: Remove invalid parentheses from string
    const arr = s.split('');
    // First remove max index to avoid breaking the index. Let's reverse it.
    stack.reverse();
    
    for (const i of stack) {
        arr.splice(i,1);
    }
    return arr.join('');
};

921. Minimum Add to Make Parentheses Valid

https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/description/

A parentheses string is valid if and only if:

• It is the empty string,
• 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.

You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.

• For example, if s = "()))", you can insert an opening parenthesis to be "(()))" or a closing parenthesis to be "())))".

Return the minimum number of moves required to make s valid.

Approach

We can take the following approach.

1. Maintain counter variable.
2. Scan each char from left to right.
3. Increment counter on left parenthesis and decrement counter on right parenthesis.
4. If counter <0then expression becomes invalid then increment the ans and reset counter=0.
5. At the end, add the leftover invalid expression needed to make it valid.

/**
 * @param {string} S
 * @return {number}
 */
var minAddToMakeValid = function (S) {
    let ans = 0;
    let counter = 0;
    for (const chr of S) {
        if (chr === '(') {
            counter++;
        }
        if (chr === ')') {
            counter--;
        }
        // if not a valid expression
        if (counter < 0) {
            ans++;
            // reset 
            counter = 0;
        }
    }
    // Add the balance
    ans += Math.abs(counter);
    return ans;
};

1963. Minimum Number of Swaps to Make the String Balanced

https://leetcode.com/problems/minimum-number-of-swaps-to-make-the-string-balanced/description

You are given a 0-indexed string s of even length n. The string consists of exactly n / 2 opening brackets '[' and n / 2 closing brackets ']'.

A string is called balanced if and only if:

• It is the empty string, or
• It can be written as AB, where both A and B are balanced strings, or
• It can be written as [C], where C is a balanced string.

You may swap the brackets at any two indices any number of times.

Return the minimum number of swaps to make s balanced.

Example 1:

Input: s = "]]][[["
Output: 2
Explanation: You can do the following to make the string balanced:
- Swap index 0 with index 4. s = "[]][][".
- Swap index 1 with index 5. s = "[[][]]".
The resulting string is "[[][]]".

Approach# Remove already balanced bracket followed by solving the remaining

Following is approach

1. For given input, first we can remove the already balanced bracket.
2. For example, [][]]][[[][] will be converted to ]][[
3. It means we only need to solve the pattern like ][ or ]][[ or ]]][[[ or ]]]][[[[
4. On manually solving we get following pattern

][       = 1
]][[     = 1
]]][[[   = 2
]]]][[[[ = 3

Based on that we can say that we need (half+1)/2 swap.

Following is code to implement this approach.

class Solution {
private:
    string getLeftover(string s) {
        vector<char> st;
        int n = s.size();
        for (int k = 0; k < n; k++) {
            if (!st.empty() && s[k] == ']' && st[st.size() - 1] == '[') {
                st.pop_back();
            } else {
                st.push_back(s[k]);
            }
        }
        return string(st.begin(), st.end());
    }
public:
    int minSwaps(string s) {
        string remaining = getLeftover(s);
        if (remaining.empty()) {
            return 0;
        }
        // Need to swap leftover only i.e. case like ]]] [[[
        int half = remaining.size() / 2;
        return (half + 1) / 2;
    }
};

Happy coding :-)