Valid Parenthesis String

Difficulty Level Medium
Frequently asked in Amazon Facebook Oracle
StringViews 1661

In the valid parenthesis string problem we have given a string containing ‘(,)‘ and ‘*‘, check if the string is balanced if ‘*‘ can be replaced with ‘(‘, ‘)‘ or an empty string.

Examples

Input
“()”
Output
true

Input
“*)”
Output
true

Input
“(*))”
Output
true

Naive Approach for Valid Parenthesis String

*‘ can take three possible values, try all these values, if there is any valid balanced string, then the current string is valid.

  1. Traverse the given string.
  2. Recursively replace ‘*‘ with ‘(‘, ‘)‘ and empty string.
  3. If any combination is a balanced string, then the given string is balanced.

Consider an example, “*)”,

Valid Parenthesis String

JAVA Code for Valid Parenthesis String

public class ValidParanthesisString {
    private static boolean ans;

    private static boolean isValid(String str) {
        // Initialise ans as false
        ans = false;
        // Recur and try all the combinations possible for the string
        recurStr(new StringBuilder(str), 0);
        return ans;
    }

    private static void recurStr(StringBuilder str, int i) {
        if (i == str.length()) {
            // check validity of the string, as it is fully formed when i = str.length()
            ans |= checkValidity(str);
        } else if (str.charAt(i) == '*') {
            // Replace * with (
            str.setCharAt(i, '(');
            recurStr(str, i + 1);
            // Replace * with )
            str.setCharAt(i, ')');
            recurStr(str, i + 1);
            // replace * with empty string
            str.setCharAt(i, ' ');
            recurStr(str, i + 1);
        } else {
            // If the current character is not * continue for next character
            recurStr(str, i + 1);
        }
    }
    
    // Function to check if given string is balanced or not
    private static boolean checkValidity(StringBuilder str) {
        int bal = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(') {
                bal++;
            } else if (str.charAt(i) == ')') {
                bal--;
            }
            if (bal < 0) {
                break;
            }
        }

        return bal == 0;
    }
    
    public static void main(String[] args) {
        // Example 1
        String str = "()";
        System.out.println(isValid(str));
        
        // Example 2
        str = "(*)";
        System.out.println(isValid(str));
        
        // Example 3
        str = "(*))";
        System.out.println(isValid(str));
    }
}

C++ Code for Valid Parenthesis String

#include <iostream>
using namespace std;

bool ans;

// Function to check if given string is balanced or not
bool checkValidity(string str) {
    int bal = 0;
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '(') {
            bal++;
        } else if (str[i] == ')') {
            bal--;
        }
        if (bal < 0)
            break;
    }
    return (bal == 0);
}

void recurStr(string str, int i) {
    if (i == str.size()) {
        // check validity of the string, as it is fully formed when i = str.length()
        ans |= checkValidity(str);
    } else if (str[i] == '*') {
        // Replace * with (
        str[i] = '(';
        recurStr(str, i + 1);
        // Replace * with )
        str[i] = ')';
        recurStr(str, i + 1);
        // replace * with empty string
        str[i] = ' ';
        recurStr(str, i + 1);
    } else {
        // If the current character is not * continue for next character
        recurStr(str, i + 1);
    }
}

bool isValid(string str) {
    // Initialise ans as false
    ans = false;
    
    // Recur and try all the combinations possible for the string
    recurStr(str, 0);
    
    return ans;
}

int main() {
  string str = "()";
    if (isValid(str)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 2
    str = "(*)";
    if (isValid(str)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 3
    str = "(*))";
    if (isValid(str)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
  return 0;
}
true
true
true

Complexity Analysis

Time Complexity = O(n * 3n
Space Complexity = O(3n), due to recursion
where n is the number of characters in the given string.

Optimal Approach for Valid Parenthesis String

For each character of the given string count the minimum and a maximum number of open brackets till this point.

  1. An open bracket increases the minimum and maximum value by 1.
  2. A close bracket decreases the minimum and maximum value by 1, lower value cannot be negative.
  3. An asterisk(*) decreases the minimum value by 1 and increases the maximum value by 1.
  4. If the maximum value becomes negative at any point, then the string is not balanced.

If the lower value of open brackets is 0, then the string is valid.

Example

Consider the string “(***)“,

  • ‘(‘ : Increases minimum and maximum by 1{Index 0} (minimum = 1, maximum = 1)
  • ‘*’ : Decreases minimum by 1 and increases maximum by 1 {Index 1, 2 and 3} (minimum = 0 and maximum = 4)
  • ‘) : Decreases minimum and maximum by 1{Index 4} (minimum = 0 and maximum = 3)

minimum is 0 at the end of traversing, so the string is valid.

JAVA Code

public class ValidParanthesisString {
    private static boolean isValid(String str) {
        // Initialise minimum and maximum as 0
        int minimum = 0, maximum = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(') {
                // Open bracket increases minimum and maximum by 1
                minimum++;
                maximum++;
            } else if (str.charAt(i) == ')') {
                // Close bracket decreases minimum and maximum by 1
                minimum--;
                maximum--;
            } else {
                // asterisk(*) decreases minimum by 1 and increases maximum by 1
                minimum--;
                maximum++;
            }
            // If maximum becomes less than 0, string is not balanced
            if (maximum < 0)
                return false;
            // minimum cannot be less than 0
            minimum = Math.max(minimum, 0);
        }
        
        // If minimum is 0, then string is balanced
        return minimum == 0;
    }
    
    public static void main(String[] args) {
        // Example 1
        String str = "()";
        System.out.println(isValid(str));

        // Example 2
        str = "(*)";
        System.out.println(isValid(str));

        // Example 3
        str = "(*))";
        System.out.println(isValid(str));
    }
}

C++ Code

#include <iostream>
using namespace std;

bool isValid(string str) {
    // Initialise minimum and maximum as 0
    int minimum = 0, maximum = 0;
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '(') {
            // Open bracket increases minimum and maximum by 1
            minimum++;
            maximum++;
        } else if (str[i] == ')') {
            // Close bracket decreases minimum and maximum by 1
            minimum--;
            maximum--;
        } else {
            // asterisk(*) decreases minimum by 1 and increases maximum by 1
            minimum--;
            maximum++;
        }
        // If maximum becomes less than 0, string is not balanced
        if (maximum < 0)
            return false;
        // minimum cannot be less than 0
        minimum = std::max(minimum, 0);
    }
    // If minimum is 0, then string is balanced
    return (minimum == 0);
}

int main() {
  string str = "()";
    if (isValid(str)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 2
    str = "(*)";
    if (isValid(str)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 3
    str = "(*))";
    if (isValid(str)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
  return 0;
}
true
true
true

Complexity Analysis for Valid Parenthesis String

Time Complexity = O(n) 
Space Complexity = O(1)
where n is the number of characters in the given string.

References

Translate »