Valid Parenthesis String - Practice Coding Problems

Valid Parenthesis String - Problem

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 "".

Input & Output

Example 1 — Basic Wildcard

$ Input: s = "()"

› Output: true

💡 Note: Simple balanced parentheses without any wildcards

Example 2 — Wildcard as Close

$ Input: s = "(*)"

› Output: true

💡 Note: The '*' can be treated as ')' to balance the '('

Example 3 — Complex Case

$ Input: s = "(*))"

› Output: true

💡 Note: The '*' can be '(' making it '(()))', then balanced by treating another as empty

Constraints

1 ≤ s.length ≤ 100
s[i] is '(', ')' or '*'

Visualization

Tap to expand

Understanding the Visualization

Input

String with '(', ')', and '*' characters

Wildcard Flexibility

Each '*' can be '(', ')', or empty

Validation

Check if any combination creates valid parentheses

Key Takeaway

🎯 Key Insight: Wildcards provide flexibility - track the range of possible states rather than trying all combinations

Asked in

G Google 25 a Amazon 20 M Microsoft 15 f Facebook 18

The key insight is treating wildcards as flexible characters. The optimal greedy approach tracks the range of possible open parentheses counts, ensuring 0 is achievable. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Two-Stack Approach	O(n)	O(n)	Use two stacks to track open parentheses and stars separately
Greedy - Balance Range Tracking	O(n)	O(1)	Track the range of possible open parentheses counts
Brute Force - Try All Combinations	O(3ⁿ)	O(n)	Try every possible assignment of '*' characters

Two-Stack Approach — Algorithm Steps

Push positions of '(' and '*' to separate stacks
For ')', pop from '(' stack first, then '*' stack
Match remaining '(' with '*' that appear after them
Valid if all '(' can be matched

Visualization

Tap to expand

Step-by-Step Walkthrough

Push to Stacks

Store positions of '(' and '*' characters

Match ')'

Match ')' with '(' first, then '*'

Final Match

Match remaining '(' with later '*'

Code -

solution.c — C

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

bool solution(const char* s) {
    int openStack[1001], openTop = -1; // positions of '('
    int starStack[1001], starTop = -1; // positions of '*'
    int len = strlen(s);
    
    // First pass: handle ')' characters
    for (int i = 0; i < len; i++) {
        char c = s[i];
        if (c == '(') {
            openStack[++openTop] = i;
        } else if (c == '*') {
            starStack[++starTop] = i;
        } else { // c == ')'
            if (openTop >= 0) {
                openTop--;
            } else if (starTop >= 0) {
                starTop--;
            } else {
                return false;
            }
        }
    }
    
    // Second pass: match remaining '(' with '*'
    while (openTop >= 0 && starTop >= 0) {
        // '(' must come before '*' for valid matching
        if (openStack[openTop] > starStack[starTop]) {
            return false;
        }
        openTop--;
        starTop--;
    }
    
    // All '(' should be matched
    return openTop < 0;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    bool result = solution(s);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass plus final matching phase

✓ Linear Growth

Space Complexity

O(n)

Two stacks can store up to n positions each

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two-Stack Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler