How do you solve Check if a Parentheses String Can Be Valid on LeetCode?

Check if a Parentheses String Can Be Valid (LeetCode #2116) 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: An odd-length parentheses string can never be valid.

What is the brute force solution for Check if a Parentheses String Can Be Valid?

The brute force approach for Check if a Parentheses String Can Be Valid is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach tries all possible combinations of changing the unlocked parentheses to see if any combination results in a valid parentheses string. This method is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Check if a Parentheses String Can Be Valid?

Check if a Parentheses String Can Be Valid uses the following concepts: String, Stack, Greedy. The recommended patterns to study are: Greedy, Two Pointers.

What are the interview tips for Check if a Parentheses String Can Be Valid?

Always clarify the problem constraints and edge cases before jumping into coding. Think about the balance of parentheses and how locked positions affect it. Practice writing helper functions for validation to keep your main logic clean.

What are common mistakes when solving Check if a Parentheses String Can Be Valid?

Not considering the locked positions correctly when counting parentheses. Failing to check both left-to-right and right-to-left balances.

#2116

Check if a Parentheses String Can Be Valid

Medium

StringStackGreedyGreedyTwo Pointers

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 to count the balance of parentheses while considering locked and unlocked positions. This method efficiently checks if the parentheses can be made valid without generating all combinations.

⚙️

Algorithm

5 steps

1Step 1: Initialize two counters: `open` for '(' and `close` for ')'.
2Step 2: Traverse the string from left to right, updating the counters based on the characters and the locked string.
3Step 3: If at any point `close` exceeds `open`, return false.
4Step 4: Traverse the string from right to left, repeating the process to ensure balance in the opposite direction.
5Step 5: If both passes are valid, return true.

solution.py33 lines

1# Full working Python code
2
3def can_be_valid(s, locked):
4    open_count = 0
5    close_count = 0
6    n = len(s)
7
8    # Left to right pass
9    for i in range(n):
10        if locked[i] == '1':
11            if s[i] == '(': open_count += 1
12            else: close_count += 1
13        else:
14            open_count += 1  # Treat unlocked as '('
15        if close_count > open_count:
16            return False
17
18    open_count = 0
19    close_count = 0
20    # Right to left pass
21    for i in range(n - 1, -1, -1):
22        if locked[i] == '1':
23            if s[i] == '(': open_count += 1
24            else: close_count += 1
25        else:
26            open_count += 1  # Treat unlocked as ')'
27        if close_count > open_count:
28            return False
29
30    return True
31
32# Example usage
33print(can_be_valid('))()))', '010100'))

ℹ

Complexity note: The time complexity is O(n) because we traverse the string twice (once from left to right and once from right to left), and the space complexity is O(1) since we only use a few variables to count.

1An odd-length parentheses string can never be valid.
2The balance of parentheses must be maintained at all times during traversal.

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