Scale Engineer

Valid Parenthesis String

Med
#0632Time: O(3^n), where n is the length of the string. In the worst case (a string of all '*'), we have 3 choices for each character, leading to an exponential number of paths.Space: O(n), for the recursion stack depth, where n is the length of the string.5 companies
Patterns
Dynamic ProgrammingGreedy
Data structures
StringStack
Companies
ServiceNowTekionAlibabaRoku

Prompt

Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.

The following rules define a valid string:

  • Any left parenthesis '(' must have a corresponding right parenthesis ')'.
  • Any right parenthesis ')' must have a corresponding left parenthesis '('.
  • Left parenthesis '(' must go before the corresponding right parenthesis ')'.
  • '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".

 

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "(*)"
Output: true

Example 3:

Input: s = "(*))"
Output: true

 

Constraints:

  • 1 <= s.length <= 100
  • s[i] is '(', ')' or '*'.

Approaches

4 approaches with complexity analysis and trade-offs.

This approach explores every possible interpretation of the '' characters. For each '', we recursively try three possibilities: treating it as an opening parenthesis '(', a closing parenthesis ')', or an empty string. This exhaustive search checks if any combination results in a valid parenthesis string.

Algorithm

  • Define a recursive function check(s, index, openCount).
  • index is the current position in the string, and openCount is the balance of open parentheses.
  • Base Case 1: If openCount becomes negative, it's an invalid state, return false.
  • Base Case 2: If index reaches the end of the string, the string is valid if and only if openCount is 0.
  • Recursive Step:
    • If s[index] is '(', recurse with check(s, index + 1, openCount + 1).
    • If s[index] is ')', recurse with check(s, index + 1, openCount - 1).
    • If s[index] is '*', explore all three possibilities by making three separate recursive calls:
      1. Treat * as '(': check(s, index + 1, openCount + 1).
      2. Treat * as ')': check(s, index + 1, openCount - 1).
      3. Treat * as empty: check(s, index + 1, openCount).
    • Return true if any of the three branches for * return true.

Walkthrough

We define a recursive function check(index, open_count) which determines if the substring starting from index is valid, given a current balance of open_count open parentheses.

  • The base case for the recursion is when we reach the end of the string (index == s.length()). The string is valid if and only if the open_count is zero.
  • Another base case is if open_count ever becomes negative, which means we have an invalid sequence (e.g., a ')' without a preceding '('). In this case, we prune the search path by returning false.
  • In the recursive step, for the character at the current index:
    • If it's '(', we increment open_count and recurse on the next index.
    • If it's ')', we decrement open_count and recurse.
    • If it's '*', we branch out and make three recursive calls: one for treating it as '(', one for ')', and one for an empty string. If any of these branches return true, the string is valid.
class Solution {    public boolean checkValidString(String s) {        return check(s, 0, 0);    }     private boolean check(String s, int index, int openCount) {        if (openCount < 0) {            return false;        }        if (index == s.length()) {            return openCount == 0;        }         char c = s.charAt(index);        if (c == '(') {            return check(s, index + 1, openCount + 1);        } else if (c == ')') {            return check(s, index + 1, openCount - 1);        } else { // c == '*'            // Try all 3 possibilities for '*'            return check(s, index + 1, openCount + 1) || // as '('                   check(s, index + 1, openCount - 1) || // as ')'                   check(s, index + 1, openCount);      // as empty        }    }}

Complexity

Time

O(3^n), where n is the length of the string. In the worst case (a string of all '*'), we have 3 choices for each character, leading to an exponential number of paths.

Space

O(n), for the recursion stack depth, where n is the length of the string.

Trade-offs

Pros

  • Simple to understand and implement the core logic.

  • Correctly explores all possibilities.

Cons

  • Extremely inefficient due to its exponential time complexity.

  • Will result in a 'Time Limit Exceeded' error on most platforms for non-trivial inputs.

Solutions

class Solution {public  boolean checkValidString(String s) {    int x = 0;    int n = s.length();    for (int i = 0; i < n; ++i) {      if (s.charAt(i) != ')') {        ++x;      } else if (x > 0) {        --x;      } else {        return false;      }    }    x = 0;    for (int i = n - 1; i >= 0; --i) {      if (s.charAt(i) != '(') {        ++x;      } else if (x > 0) {        --x;      } else {        return false;      }    }    return true;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem