How do you solve Valid Parenthesis String on LeetCode?

Valid Parenthesis String (LeetCode #678) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Understanding how '*' can represent multiple characters is crucial.

What is the brute force solution for Valid Parenthesis String?

The brute force approach for Valid Parenthesis String is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach explores all possible ways to interpret the '*' characters in the string. Since '*' can represent '(', ')', or an empty string, we can generate all combinations and check if any of them form a valid parentheses string. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Valid Parenthesis String?

Valid Parenthesis String uses the following concepts: String, Dynamic Programming, Stack, Greedy. The recommended patterns to study are: Greedy, Dynamic Programming.

What are the interview tips for Valid Parenthesis String?

Explain your thought process clearly when discussing the problem. Be prepared to discuss edge cases, such as strings with only '*' characters. Practice writing both brute force and optimal solutions to understand the trade-offs.

What are common mistakes when solving Valid Parenthesis String?

Not considering all possible interpretations of '*'. Failing to reset the low counter when it goes negative.

#678

Valid Parenthesis String

Medium

StringDynamic ProgrammingStackGreedyGreedyDynamic Programming

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution uses a greedy approach with two counters to track the balance of parentheses. By treating '*' as either '(' or ')' or ignoring it, we can efficiently determine if the string can be valid without generating all combinations.

⚙️

Algorithm

4 steps

1Step 1: Initialize two counters: 'low' and 'high'. 'low' tracks the minimum possible open parentheses, and 'high' tracks the maximum possible open parentheses.
2Step 2: Iterate through each character in the string: - If it's '(': increment both 'low' and 'high'. - If it's ')': decrement both 'low' and 'high'. - If it's '*': decrement 'low' (considering it as ')') and increment 'high' (considering it as '(').
3Step 3: At any point, if 'high' < 0, return false (too many closing parentheses). If 'low' < 0, reset 'low' to 0 (we can ignore some open parentheses).
4Step 4: At the end of the iteration, if 'low' is 0, return true (valid string); otherwise, return false.

solution.py12 lines

1# Full working Python code
2
3def checkValidString(s):
4    low = 0
5    high = 0
6    for char in s:
7        if char == '(': low += 1
8        else: low -= 1
9        high += 1 if char == '*' else -1
10        if high < 0: return False
11        low = max(low, 0)
12    return low == 0

ℹ

Complexity note: The time complexity is O(n) because we make a single pass through the string. The space complexity is O(1) since we only use a fixed amount of extra space for the counters.

1Understanding how '*' can represent multiple characters is crucial.
2Using counters to track possible balances is an efficient way to validate parentheses.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.