MediumStringDynamic ProgrammingStackGreedyBracket SequencesUpdated Sep 2026

678. Valid Parenthesis String

Asked at Apple

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

String

Companies

1

Problem

You are given a string s made of three kinds of characters: '(', ')' and '*'.

A string is valid when every '(' has a matching ')' that comes after it, every ')' has a matching '(' before it, and the pairs do not cross. The '*' character is special: you may treat each '*' as '(', as ')', or as an empty string. You can choose a different meaning for each '*'.

Return true if there is at least one way to replace every '*' so that the whole string becomes valid. Otherwise return false. An empty string is valid, but here the length is at least 1.

Stars give you choices

s(*))0123The '*' is the only flexible position in this example'*' as '(' → "(())" valid'*' as ')' → "())" invalid'*' as '' → "()" validTwo of the three choices work, so the answer is true
Each '*' can act as '(', as ')' or as nothing, and we only need one good choice to answer true.

Constraints

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

Examples

Example 1
Inputs = "()"
Outputtrue
WhyThere is no star here. The '(' is closed by the ')' that follows it, so the string is already valid.
Example 2
Inputs = "(*)"
Outputtrue
WhyTreat the '*' as an empty string. Then the string becomes "()", which is valid.
Example 3
Inputs = "(*))"
Outputtrue
WhyTreat the '*' as '('. The string becomes "(())", and the two pairs are properly nested, so it is valid.
Example 4
Inputs = "("
Outputfalse
WhyThere is only one character and it is an opening bracket with nothing to close it, so no replacement can make it valid.

Asked At

1 companies
CompanyDifficulty
AppleMediumView all Apple questions →

How to Think About It

1

Brute force: try all possible replacements of * (three choices each) and check validity.

2

DP approach: dp[i][j] = true if substring s[i..j] is valid. Base: single * is valid, empty is valid.

3

Greedy with two counters: track the range of possible open parentheses counts.

4

Low tracks minimum open count (treat * as ")"), high tracks maximum open count (treat * as "(").

5

At the end, low must be 0. If high ever goes negative, return false early.

Optimal Approach

Use two counters: low and high. low represents the minimum possible open parentheses, high the maximum. For "(", increment both. For ")", decrement both. For "*", decrement low and increment high (simulating all three choices). Clamp low to 0. If high goes below 0, return false. At the end, low == 0 means a valid string exists. O(n) time, O(1) space.

Track the range of open brackets

s(*))0123iStart at i = 0 with low = 0, high = 0low / highlowhigh(*))11020100After the last ')', low = 0 and high = 0, so a validchoice exists'(' → low+1, high+1')' → low = max(low-1, 0), high-1'*' → low = max(low-1, 0), high+1high < 0 → false; end: low == 0
low and high are the smallest and largest possible number of open brackets after each character.
ComplexityTime O(n)Space O(1)We scan the string once and only keep two integer counters, so the cost is linear in the length and constant in extra memory.

What Trips People Up in Real Interviews

1

Clarify: can * appear anywhere, including at the start or end.

2

The greedy two-pointer approach is the most elegant and runs in O(n) time.

3

DP is O(n^2) time and space — acceptable but less efficient.

4

Be careful: low should never go below 0 (clamp it).

5

If high is negative at any point, it means too many ")" have appeared — return false.

Solution Code

O(n) time
class Solution:
    def checkValidString(self, s: str) -> bool:
        low = high = 0
        for ch in s:
            if ch == '(':
                low += 1
                high += 1
            elif ch == ')':
                low = max(low - 1, 0)
                high -= 1
            else:
                low = max(low - 1, 0)
                high += 1
            if high < 0:
                return False
        return low == 0

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Valid Parenthesis String problem?

Given a string s containing characters "(" , ")" , and "*", determine if the string is valid. An empty string is valid. Each "(" must have a matching ")" in the correct order. "*" can be treated as "(", ")", or an empty string.

How do you solve Valid Parenthesis String?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Valid Parenthesis String?

Valid Parenthesis String is asked at Apple. It is a medium difficulty problem.

What are common mistakes on Valid Parenthesis String?
  • Clarify: can * appear anywhere, including at the start or end.
  • The greedy two-pointer approach is the most elegant and runs in O(n) time.
  • DP is O(n^2) time and space — acceptable but less efficient.
  • Be careful: low should never go below 0 (clamp it).
  • If high is negative at any point, it means too many ")" have appeared — return false.