Valid Parenthesis String

Valid Parenthesis String adds a twist to the classic balance check. There is a wildcard that can be anything. So people panic and try every choice for it. But there is a calm way to handle uncertainty. Track a range of how open the string could be. That one idea makes the wildcard easy.

🎯 The Problem

You get a string of three characters only and check if it can be balanced.

• The characters are open (, close ), and star *.
• A star is a wildcard. It can become (, ), or nothing.
• You choose what each star becomes.
• Balanced means every open has a matching close later, nested correctly.
• You return true or false.

Let us say the string is (*)). The star can become an open bracket. Then we have (()) which is balanced. So the answer is true.

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

Explanation: the star becomes '(', giving "(())" which is balanced

The hard part is the star. It has three possible meanings. So at each star the string splits into three futures. We need a way to handle all of them at once.

Here is the shape of the problem. Each star has three possible roles.

🐢 Approach 1: Try Every Star Meaning (Brute Force)

The idea in one line: branch each star into all three meanings and test if any full string balances.

The idea:

• Each star can be (, ), or empty.
• Branch into all three at every star.
• Check if any final string is balanced.

Why it is weak:

• Every star multiplies the string count by three.
• With many stars the count explodes.
• Far too many futures to test one by one.

Here is the brute-force recursive code:

def check_valid_string(s):
    def dfs(index, balance):
        if balance < 0:
            return False
        if index == len(s):
            return balance == 0
        if s[index] == "(":
            return dfs(index + 1, balance + 1)
        if s[index] == ")":
            return dfs(index + 1, balance - 1)
        return dfs(index + 1, balance) or dfs(index + 1, balance + 1) or dfs(index + 1, balance - 1)

    return dfs(0, 0)

⚡ Approach 2: Greedy Low and High Range (Best)

The idea in one line: never commit a star, just track the range of how many open brackets could still be waiting.

The idea:

• The open count is how many ( have no partner yet.
• A star makes that count uncertain.
• So track a range, not one number.
• Low is the smallest the open count could be.
• High is the largest it could be.

How it works:

• Sweep the string one character at a time.
• For (, add one to both low and high.
• For ), subtract one from both low and high.
• For *, subtract one from low and add one to high.
• If high goes below zero, return false at once.
• Never let low go below zero. Clamp it back.

Why it works:

• High below zero means too many close brackets, no choice saves it.
• Clamping low quietly drops the star choices that over-close.
• Low ending at zero means a valid star choice leaves nothing open.

Why it is fast:

• One sweep and two counters.
• So the time is O(n) and the space is O(1).

Here is a dry run on (*)). Watch low and high move as we read each character.

Steps to Solve

1. Start two counters, low and high, both at zero.
2. Read the string one character at a time.
3. For (, add one to both low and high.
4. For ), subtract one from both low and high.
5. For *, subtract one from low and add one to high.
6. If high goes below zero, return false right away.
7. If low goes below zero, clamp it back to zero.
8. At the end, return true only if low is zero.

#include <stdio.h>
#include <string.h>

int checkValidString(const char *s) {
    int low = 0, high = 0;          // smallest and largest open count
    int n = strlen(s);

    for (int i = 0; i < n; i++) {
        char c = s[i];
        if (c == '(') {
            low++; high++;          // a real open bracket
        } else if (c == ')') {
            low--; high--;          // a real close bracket
        } else {                    // a star
            low--; high++;          // could close or open
        }
        if (high < 0) return 0;     // too many close brackets
        if (low < 0) low = 0;       // cannot go below zero
    }

    return low == 0;                // any valid choice leaves nothing open?
}

int main(void) {
    const char *s = "(*))";
    printf("%s\n", checkValidString(s) ? "true" : "false");
    return 0;
}

true

#include <iostream>
#include <string>
using namespace std;

bool checkValidString(string s) {
    int low = 0, high = 0;          // smallest and largest open count

    for (char c : s) {
        if (c == '(') {
            low++; high++;          // a real open bracket
        } else if (c == ')') {
            low--; high--;          // a real close bracket
        } else {                    // a star
            low--; high++;          // could close or open
        }
        if (high < 0) return false; // too many close brackets
        if (low < 0) low = 0;       // cannot go below zero
    }

    return low == 0;                // any valid choice leaves nothing open?
}

int main() {
    string s = "(*))";
    cout << (checkValidString(s) ? "true" : "false") << endl;
    return 0;
}

true

public class ValidParenthesisString {
    public static boolean checkValidString(String s) {
        int low = 0, high = 0;          // smallest and largest open count

        for (char c : s.toCharArray()) {
            if (c == '(') {
                low++; high++;          // a real open bracket
            } else if (c == ')') {
                low--; high--;          // a real close bracket
            } else {                    // a star
                low--; high++;          // could close or open
            }
            if (high < 0) return false; // too many close brackets
            if (low < 0) low = 0;       // cannot go below zero
        }

        return low == 0;                // any valid choice leaves nothing open?
    }

    public static void main(String[] args) {
        String s = "(*))";
        System.out.println(checkValidString(s) ? "true" : "false");
    }
}

true

def check_valid_string(s):
    low = 0          # smallest possible open count
    high = 0         # largest possible open count

    for c in s:
        if c == '(':
            low += 1
            high += 1            # a real open bracket
        elif c == ')':
            low -= 1
            high -= 1            # a real close bracket
        else:                    # a star
            low -= 1             # if it closes or is empty
            high += 1            # if it opens
        if high < 0:             # too many close brackets
            return False
        if low < 0:              # cannot go below zero
            low = 0

    return low == 0              # a valid star choice leaves nothing open


s = "(*))"
print(check_valid_string(s))

True

function checkValidString(s) {
  let low = 0; // smallest possible open count
  let high = 0; // largest possible open count

  for (const c of s) {
    if (c === "(") {
      low++;
      high++; // a real open bracket
    } else if (c === ")") {
      low--;
      high--; // a real close bracket
    } else {
      low--; // star closes or is empty
      high++; // star opens
    }
    if (high < 0) return false; // too many close brackets
    if (low < 0) low = 0; // cannot go below zero
  }

  return low === 0; // a valid star choice leaves nothing open
}

const s = "(*))";
console.log(checkValidString(s));

true

Let us read the Python version line by line, because the range idea is the whole trick.

We start low = 0 and high = 0. Low is the smallest the open count could be across all star choices. High is the largest it could be. At the start nothing is open, so both are zero.

Then we loop over each character c. For ( we do low += 1 and high += 1. A real open bracket adds one waiting bracket no matter what, so both ends of the range rise.

For ) we do low -= 1 and high -= 1. A real close bracket removes one waiting bracket no matter what, so both ends fall.

For the star we do low -= 1 and high += 1. This is the key line. If we read the star as a close bracket or as empty, the open count could be lower, so low drops. If we read it as an open bracket, the open count could be higher, so high rises. The single star widens the whole range.

Then the guard if high < 0: return False. If even the most generous reading has more close brackets than open ones, no choice can save the string. So we stop and return False.

Next if low < 0: low = 0. The open count can never truly be negative. So when low dips under zero we clamp it back. This means we quietly drop the star choices that would have over-closed the string.

At the end return low == 0. If low is zero, there exists a way to pick the stars that leaves no bracket open. So the string is balanceable and we return True.

⏱️ Time and Space Complexity

The brute force branches three ways at every star, so its time becomes unusable fast. The greedy range version reads the string once and keeps just two counters. So it runs in O(n) time and uses constant extra space.

🧩 Key Takeaways

• ✅ The open count is how many open brackets are still waiting for a partner.
• ✅ A star makes the open count uncertain, so track a low and a high range instead of one number.
• ✅ A real ( raises both ends, a real ) lowers both ends, and a star lowers low while raising high.
• ✅ If high ever goes below zero, stop and return false, because there are too many close brackets.
• ✅ The string is balanceable only if low ends at zero.

🚀 What’s Next?

• Merge Triplets to Form Target Triplet
• Hand of Straights