Skip to main content
Talentd

Valid Parenthesis String - Solution & Explanation

MediumStringDynamic ProgrammingStackGreedy13 min readAsked at: Amazon, Microsoft, Apple +13
Practice this problem

Problem Statement

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 '*'.

Approach Overview

Problem Overview: You receive a string containing three characters: (, ), and *. The asterisk acts as a wildcard and can represent (, ), or an empty string. The task is to determine whether the string can be interpreted as a valid parentheses sequence.

This problem looks like a typical parentheses validation task but becomes tricky because * can play multiple roles. You need a strategy that keeps track of possible interpretations without trying every combination. Efficient solutions rely on techniques from stack processing and greedy algorithms, both commonly used when validating structured strings.

Approach 1: Stack-based Tracking (O(n) time, O(n) space)

This approach uses two stacks: one for indices of ( characters and another for indices of *. While iterating through the string, push positions of opening brackets and asterisks onto their respective stacks. When encountering ), try to match it with the most recent (. If none exists, use a * as a substitute opening bracket. After processing the entire string, there may still be unmatched (. Pair them with later * characters by comparing indices to ensure ordering is valid. This approach works because stacks naturally model the nested structure of parentheses while allowing deferred decisions for wildcard characters.

Approach 2: Greedy Balance Range (O(n) time, O(1) space)

The greedy solution tracks the range of possible open-parenthesis counts instead of exact matches. Maintain two counters: low (minimum possible open brackets) and high (maximum possible open brackets). When reading (, increment both. When reading ), decrement both. When reading *, treat it flexibly: decrement low (as if it were )) and increment high (as if it were (). Clamp low to zero because open counts cannot be negative. If high ever drops below zero, the string cannot be valid. By the end of the scan, a valid configuration exists if low == 0. This method works because it keeps track of the entire feasible range of interpretations without explicitly constructing them.

Recommended for interviews: The greedy balance method is the solution most interviewers expect. It runs in O(n) time with O(1) space and demonstrates strong reasoning about state ranges rather than brute-force enumeration. The stack-based approach is still valuable during interviews because it shows clear thinking about matching order and wildcard handling, but the greedy method highlights deeper optimization skills.

Approach 1: Stack-based Approach

In this approach, we use two stacks. One stack will store indices of '(' characters, and the other will store indices of '*' characters as we traverse the string.

If we find a ')' character and there are unmatched '(' in the stack, we pop one out as it can be matched. If no '(' is available, we match using '*'. After processing, all unmatched '(' should be balanced by '*' appearing after them in the string.

The function uses two stacks to keep track of the positions of '(' and '*' characters. When encountering ')', it attempts to match it using an available '(' or '*'. After scanning the string, any remaining unmatched '(' is checked against '*' to ensure validity.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n), as we process each character of the string once.
Space Complexity: O(n), due to use of two stacks to track indices of '(' and '*'.

Try this approach in the editor →

Approach 2: Greedy Approach with Balances

This approach involves maintaining two balance counts: one for keeping a minimal balance and the other for maximal considering '*' as both '(' and ')'.

As we traverse, the minimal balance ensures ')' never exceeds '(' without the aid of '*', while the maximal balance accounts for replacing '*' with '('. If at any point the maximal balance is negative, then parentheses can't be balanced.

The C++ solution uses two balance counters. It iterates over the string adjusting minBal and maxBal based on the character encountered ('(', ')', or '*'). The maxBal ensures we never have more ')' than possible '('. Negative minBal is reset to reflect reality where '*' can become '(' or empty.

Code

C++C#

C++

C#

Complexity

Time Complexity: O(n), as we traverse the string once.
Space Complexity: O(1), since we use a constant amount of extra space regardless of the input size.

Try this approach in the editor →

Approach 3: Dynamic Programming

Let dp[i][j] be true if and only if the interval s[i], s[i+1], ..., s[j] can be made valid. Then dp[i][j] is true only if:

  • s[i] is '*', and the interval s[i+1], s[i+2], ..., s[j] can be made valid;

  • or, s[i] can be made to be '(', and there is some k in [i+1, j] such that s[k] can be made to be ')', plus the two intervals cut by s[k] (s[i+1: k] and s[k+1: j+1]) can be made valid;

  • Time Complexity: O(n^3), where n is the length of the string. There are O(n^2) states corresponding to entries of dp, and we do an average of O(n) work on each state.

  • Space Complexity: O(n^2).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Approach 4: Greedy

Scan twice, first from left to right to make sure that each of the closing brackets is matched successfully, and second from right to left to make sure that each of the opening brackets is matched successfully.

  • Time Complexity: O(n), where n is the length of the string.
  • Space Complexity: O(1).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Stack-based Approach

Time Complexity: O(n), as we process each character of the string once.
Space Complexity: O(n), due to use of two stacks to track indices of '(' and '*'.

Greedy Approach with Balances

Time Complexity: O(n), as we traverse the string once.
Space Complexity: O(1), since we use a constant amount of extra space regardless of the input size.

Dynamic Programming—
Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Stack-based TrackingO(n)O(n)When you want a clear simulation of matching parentheses and explicit index tracking.
Greedy Balance RangeO(n)O(1)Preferred for interviews and production due to constant space and elegant range tracking.

Video Solution

L11. Valid Parenthesis String | Multiple Approaches • take U forward • 221,140 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Valid Parenthesis String easy or hard?
Valid Parenthesis String is classified as a medium difficulty problem. The challenge comes from handling the '*' wildcard efficiently without trying every possible replacement. Recognizing the greedy balance technique usually unlocks the optimal solution.
Valid Parenthesis String Python/Java solution
Typical implementations are written using stacks in Python or JavaScript, or a greedy counter approach in languages like C++ and C#. Both approaches run in linear time, but the greedy method is usually preferred due to constant space usage.
How to solve Valid Parenthesis String in O(n)?
Scan the string while maintaining two counters: the minimum and maximum possible open parentheses. Treat '*' as flexible by decreasing the minimum count and increasing the maximum count. If the maximum count becomes negative the string is invalid, and the string is valid at the end if the minimum count is zero.
What is the best approach for Valid Parenthesis String?
The greedy balance range approach is considered the optimal solution. It scans the string once while tracking the minimum and maximum possible number of open parentheses. This method runs in O(n) time and O(1) space, making it more efficient than stack-based methods that require extra memory.
Is Valid Parenthesis String asked at Google/Amazon/Meta?
Valid Parenthesis String frequently appears in interviews at major tech companies including Amazon, Google, and Meta. The problem tests understanding of greedy algorithms, stack-based parsing, and reasoning about multiple possible states in a single pass.
What data structure is used in Valid Parenthesis String?
Common implementations use stacks to track indices of '(' and '*' characters while matching parentheses. The optimized solution replaces explicit data structures with two integer counters that represent the range of possible open parentheses.
What is the time complexity of Valid Parenthesis String?
The optimal solutions run in O(n) time where n is the length of the string. Both the stack-based and greedy balance approaches iterate through the string once. The stack method uses O(n) space while the greedy approach reduces space complexity to O(1).

Ready to solve this problem?

Practice Valid Parenthesis String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Check if a Parentheses String Can Be Valid

Next

Special Binary String