Solution For Valid Parenthesis String

The Valid Parenthesis String problem on LeetCode is a problem in which one has to determine whether a given string of parentheses is valid or not. The string is considered valid if each open bracket has a corresponding closing bracket and the brackets are properly nested.

Here is a detailed solution to the problem:

Approach 1: Using a stack and backtracking

One way to check if a given string of parentheses is valid is to use a stack. Whenever we encounter an opening bracket, we push it onto the stack. Whenever we encounter a closing bracket, we pop an opening bracket from the stack. If the stack is empty at the end of the string, then the string is valid. Here is the pseudocode for this approach:

1. Create an empty stack.
2. Iterate through each character in the string:
   a. If the character is an opening bracket, push it onto the stack.
   b. If the character is a closing bracket, pop an opening bracket from the stack.
   c. If the stack is empty, the string is invalid. Return false.
3. If the stack is not empty, the string is invalid. Return false.
4. If the stack is empty, the string is valid. Return true.

One problem with this approach is that it doesn’t handle wildcard characters (‘*’). A wildcard character can be either an opening, closing, or empty bracket. To handle wildcard characters, we need to use backtracking. We try every possible combination of brackets and check if any of them result in a valid string. Here is the pseudocode for the backtracking approach:

1. Define a recursive function checkValid(index, openCount, closeCount):
   a. If index == n (the length of the string):
   i. If openCount == closeCount, return true.
   ii. Otherwise, return false.
   b. If the character at index is ‘(‘, call checkValid(index+1,openCount+1,closeCount).
   c. If the character at index is ‘)’:
   i. If openCount > closeCount, call checkValid(index+1,openCount,closeCount+1).
   ii. If openCount < closeCount, return false.
   iii. If openCount == closeCount, try both options (call checkValid(index+1,openCount+1,closeCount) and checkValid(index+1,openCount,closeCount+1)).
   d. If the character at index is ‘*’, try all three options (opening, closing, or empty bracket) and call checkValid in each case.
2. Call the checkValid function with initial values (0,0,0).

The time complexity of this approach is exponential because we check every possible combination of brackets. The space complexity is O(n) because of the recursive function call stack.

Approach 2: Greedy approach

A better approach to solve this problem is to use a greedy approach. We keep track of the minimum and maximum possible number of opening brackets needed to balance the remaining string of brackets at each index. If at any step, the number of closing brackets exceeds the maximum number of opening brackets, the string is invalid. If at the end of the string, the number of opening brackets is less than the minimum possible number of opening brackets, the string is invalid. Otherwise, the string is valid. Here is the pseudocode for this approach:

1. Initialize two variables: minOpenCount = 0 (minimum possible number of opening brackets needed), maxOpenCount = 0 (maximum possible number of opening brackets needed).
2. Iterate through each character in the string:
   a. If the character is ‘(‘, increment both minOpenCount and maxOpenCount.
   b. If the character is ‘)’, decrement both minOpenCount and maxOpenCount.
   c. If the character is ‘*’, try all three options (opening, closing, or empty bracket) and update minOpenCount and maxOpenCount accordingly:
   i. If we use a closing bracket, decrement both minOpenCount and maxOpenCount.
   ii. If we use an opening bracket, increment both minOpenCount and maxOpenCount.
   iii. If we use an empty bracket, decrement minOpenCount and increment maxOpenCount.
   d. If maxOpenCount becomes negative, the string is invalid. Return false.
   e. At the end of the string, if minOpenCount is not zero, the string is invalid. Otherwise, the string is valid. Return true.

The time complexity of this approach is O(n) because we iterate through the string only once. The space complexity is O(1) because we use only two variables to keep track of the minimum and maximum possible number of opening brackets.

Step by Step Implementation For Valid Parenthesis String

public boolean checkValidString(String s) {
    Stack stack = new Stack<>();
    Stack starStack = new Stack<>();
    char[] arr = s.toCharArray();
    
    for(int i = 0; i < arr.length; i++) {
        if(arr[i] == '(') {
            stack.push(i);
        } else if (arr[i] == '*') {
            starStack.push(i);
        } else {
            if(!stack.isEmpty()) {
                stack.pop();
            } else if(!starStack.isEmpty()) {
                starStack.pop();
            } else {
                return false;
            }
        }
    }
    
    while(!stack.isEmpty() && !starStack.isEmpty()) {
        if(stack.peek() > starStack.peek()) {
            return false;
        }
        stack.pop();
        starStack.pop();
    }
    
    return stack.isEmpty();
}

def checkValidString(s):
        # The number of open left brackets.
        cmin = cmax = 0
        for i in range(len(s)):
            if s[i] == '(':
                # Increment the minimum and maximum number of open left brackets.
                cmin += 1
                cmax += 1
            elif s[i] == ')':
                # Decrement the minimum and maximum number of open left brackets.
                cmax -= 1
                cmin = max(cmin - 1, 0)
            elif s[i] == '*':
                # Decrement the maximum number of open left brackets or increment the minimum number of open left brackets.
                cmax += 1
                cmin = max(cmin - 1, 0)
            if cmax < 0:
                # If the maximum number of open left brackets is less than 0 at any point, return False.
                return False
        return cmin == 0

var isValid = function(s) {
    let stack = [];
    let map = {
        "(": ")",
        "[": "]",
        "{": "}"
    }
    
    for(let i = 0; i < s.length; i++) {
        let el = s[i];
        
        if(map[el]) {
            stack.push(map[el]);
        } else {
            if(el !== stack.pop()) {
                return false;
            }
        }
    }
    
    return stack.length === 0;
};

class Solution {
public:
    bool checkValidString(string s) {
        int cmin = 0, cmax = 0; // cmin is the minimum number of open parentheses needed, cmax is the maximum
        for (char c : s) {
            if (c == '(') {
                cmin++;
                cmax++;
            } else if (c == ')') {
                cmax--;
                cmin = max(cmin - 1, 0);
            } else {
                cmax++;
                cmin = max(cmin - 1, 0);
            }
            if (cmax < 0) return false;
        }
        return cmin == 0;
    }
};

public class Solution {
    public bool CheckValidString(string s) {
        // we use a stack to keep track of the indices of the left parentheses
        Stack leftParentheses = new Stack();
        
        // we use a stack to keep track of the indices of the left asterisks
        Stack leftAsterisks = new Stack();
        
        // we iterate through the string
        for (int i = 0; i < s.Length; i++) {
            // if we encounter a left parentheses, we push its index to the stack
            if (s[i] == '(') {
                leftParentheses.Push(i);
            }
            // if we encounter a left asterisk, we push its index to the stack
            else if (s[i] == '*') {
                leftAsterisks.Push(i);
            }
            // if we encounter a right parentheses
            else {
                // if there are no left parentheses in the stack,
                // we check if there are any left asterisks in the stack
                if (leftParentheses.Count == 0) {
                    // if there are no left asterisks in the stack either,
                    // the string is not valid
                    if (leftAsterisks.Count == 0) {
                        return false;
                    }
                    // if there are left asterisks in the stack,
                    // we pop one from the stack
                    else {
                        leftAsterisks.Pop();
                    }
                }
                // if there are left parentheses in the stack,
                // we pop one from the stack
                else {
                    leftParentheses.Pop();
                }
            }
        }
        
        // we iterate through the remaining left parentheses in the stack
        while (leftParentheses.Count > 0) {
            // we check if there are any left asterisks in the stack
            if (leftAsterisks.Count == 0) {
                // if there are no left asterisks in the stack,
                // the string is not valid
                return false;
            }
            // if the index of the left asterisk in the stack is smaller than the index of the left parentheses,
            // the string is not valid
            else if (leftAsterisks.Peek() < leftParentheses.Peek()) {
                return false;
            }
            // if the index of the left asterisk in the stack is greater than the index of the left parentheses,
            // we pop the left asterisk from the stack
            else {
                leftAsterisks.Pop();
            }
            // we pop the left parentheses from the stack
            leftParentheses.Pop();
        }
        
        // if we've reached this point, it means the string is valid
        return true;
    }
}