Parenthesis problems are a staple of coding interviews and algorithm practice. They test your understanding of stacks, recursion, and string manipulation. In this post, I’ll walk you through some classic and challenging LeetCode parenthesis questions, from easy to hard, with sample Python solutions.
Problem:
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if:
Example:
Python Solution:
class Solution:
def isValid(self, s: str) -> bool:
bracket_map = {')':'(',']':'[','}':'{'}
st = []
for c in s:
if c not in bracket_map:
st.append(c)
else:
if not st or st[-1] != bracket_map[c]:
return False
st.pop()
return not st
Time Complexity: O(n)
Space Complexity: O(n) (stack)
Edge Cases:
Problem:
Given a string containing '(', ')', and '*', where '*' can be treated as '(', ')', or an empty string, determine if the string is valid.
Example:
Python Solution:
class Solution:
def checkValidString(s: str) -> bool:
def isValid(opening, closing, s):
open_cnt = 0
for c in s:
if c == opening or c == "*":
open_cnt += 1
elif c == closing:
if open_cnt <= 0:
return False
open_cnt -= 1
return True
return isValid("(", ")", s) and isValid(")", "(", s[::-1])
Explanation:
We scan the string twice: left-to-right and right-to-left, treating '*' as both open and close. This greedy approach ensures every ')' can be matched.
Time Complexity: O(n)
Space Complexity: O(1)
Edge Cases:
Problem:
Given n pairs of parentheses, generate all combinations of well-formed parentheses.
Example:
Python Solution:
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
out = []
def dfs(open, close, path):
if close == n:
if open == close:
out.append("".join(path))
return
if open < n:
dfs(open + 1, close, path + ["("])
if close < open:
dfs(open, close+1, path + [")"])
dfs(0, 0, [])
return out
Explanation:
This uses backtracking to generate all valid combinations, ensuring that at any time, the number of closing parentheses does not exceed the number of opening ones.
Time Complexity: O(4^n / √n) (Catalan number)
Space Complexity: O(n) (recursion stack)
Edge Cases:
Problem:
Given a string with parentheses and lowercase letters, remove the minimum number of brackets to make it valid.
Example:
Python Solution:
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
def getValid(s, openb):
rs = []
open_cnt = 0
for c in s:
if c == openb:
open_cnt += 1
rs.append(c)
elif c == '(' or c == ')':
if open_cnt > 0:
open_cnt -= 1
rs.append(c)
else:
rs.append(c)
return "".join(rs)
s = getValid(s, "(") # Remove invalid ')'
s = getValid(s[::-1], ")") # Remove invalid '(' (reverse string)
return s[::-1]
Explanation:
Time Complexity: O(n)
Space Complexity: O(n)
Edge Cases:
Problem:
Return the minimum number of additions needed to make parentheses valid.
Example:
Python Solution:
class Solution:
def minAddToMakeValid(self, s: str) -> int:
ans, open = 0, 0
for c in s:
if c == "(":
open += 1
else:
if open > 0:
open -= 1
else:
ans += 1
return ans + open
Explanation:
Track unmatched opening and closing brackets.
Time Complexity: O(n)
Space Complexity: O(1)
Edge Cases:
Problem:
Find the length of the longest valid parentheses substring.
Example:
Python Solution:
class Solution:
def longestValidParentheses(self, s: str) -> int:
def validLen(s, left_paren):
ans = left = right = 0
for c in s:
if c == left_paren:
left += 1
else:
right += 1
if left == right:
ans = max(ans, left * 2)
elif right > left:
left = right = 0
return ans
return max(validLen(s, "("), validLen(s[::-1], ")"))
Explanation:
Two passes (left-to-right and right-to-left) to catch all valid substrings.
Time Complexity: O(n)
Space Complexity: O(1)
Edge Cases:
Problem:
Remove the minimum number of brackets to make the string valid. Return all possible results.
Example:
Python Solution:
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
left, right = 0, 0
for c in s:
if c == "(":
left += 1
elif c == ")":
if left > 0:
left -= 1
else:
right += 1
valid_len = len(s) - left - right
ans = set()
def rec(index, opn, valid_len, path):
if valid_len == 0:
if opn == 0: ans.add("".join(path))
return
if index == len(s):
return
char = s[index]
if char == "(":
# Include '('
path.append(char)
rec(index + 1, opn + 1, valid_len - 1, path)
path.pop()
# Skip '('
rec(index + 1, opn, valid_len, path)
elif char == ")":
if opn > 0:
# Include ')'
path.append(char)
rec(index + 1, opn - 1, valid_len - 1, path)
path.pop()
# Skip ')'
rec(index + 1, opn, valid_len, path)
else:
# Include non-parenthesis character
path.append(char)
rec(index + 1, opn, valid_len - 1, path)
path.pop()
rec(0, 0, valid_len, [])
return list(ans)
Explanation:
Backtracking to generate all valid combinations by removing excess brackets.
Time Complexity: O(2^n) (worst case)
Space Complexity: O(n) (recursion stack)
Edge Cases:
Happy Coding!
Follow me for more algorithm insights and Python solutions!