Is Check if a Parentheses String Can Be Valid easy or hard?

The problem is rated Medium on LeetCode. The main challenge is recognizing that unlocked characters act as wildcards and require validating both prefix and suffix feasibility. Once the greedy insight is clear, the implementation becomes straightforward.

Check if a Parentheses String Can Be Valid Python/Java solution

Python and Java implementations typically use the greedy two-pass technique. Maintain a balance counter during a forward scan and another during a backward scan. Each character is processed once per pass, making the implementation concise and efficient for large strings.

How to solve Check if a Parentheses String Can Be Valid in O(n)?

Perform two greedy scans. In the forward pass, ensure the number of closing parentheses never exceeds the possible openings by treating unlocked characters as '('. In the backward pass, ensure openings never exceed possible closings by treating unlocked characters as ')'. If both passes succeed, the string can be made valid in O(n) time.

What is the best approach for Check if a Parentheses String Can Be Valid?

The best approach is a greedy two-pass validation that scans the string from left to right and then from right to left. Unlocked characters are treated as flexible parentheses that can adjust to maintain balance. This ensures every prefix and suffix can be made valid. The algorithm runs in O(n) time with O(1) space.

Is Check if a Parentheses String Can Be Valid asked at Google/Amazon/Meta?

Parentheses validation and greedy balance problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving locked characters or flexible replacements test deeper understanding of greedy constraints and stack-based reasoning.

What data structure is used in Check if a Parentheses String Can Be Valid?

The optimized solution does not require a complex data structure and relies on simple counters. Alternative implementations may use stacks or hash-based sets to track indices of unmatched parentheses and unlocked positions for replacement.

What is the time complexity of Check if a Parentheses String Can Be Valid?

The optimal solution runs in O(n) time because the string is scanned at most twice. Each pass performs constant-time operations per character. Space complexity is O(1) when using the greedy counter technique, or O(n) if storing indices using a hash or stack structure.

Description Hints 3 Solution Video 20:41

2116. Check if a Parentheses String Can Be Valid

Medium45.1% acceptance7 companies

A parentheses string is a non-empty string consisting only of '(' and ')'. It is valid if any of the following conditions is true:

It is ().
It can be written as AB (A concatenated with B), where A and B are valid parentheses strings.
It can be written as (A), where A is a valid parentheses string.

You are given a parentheses string s and a string locked, both of length n. locked is a binary string consisting only of '0's and '1's. For each index i of locked,

If locked[i] is '1', you cannot change s[i].
But if locked[i] is '0', you can change s[i] to either '(' or ')'.

Return true if you can make s a valid parentheses string. Otherwise, return false.

Example 1:

Input: s = "))()))", locked = "010100"
Output: true
Explanation: locked[1] == '1' and locked[3] == '1', so we cannot change s[1] or s[3].
We change s[0] and s[4] to '(' while leaving s[2] and s[5] unchanged to make s valid.

Example 2:

Input: s = "()()", locked = "0000"
Output: true
Explanation: We do not need to make any changes because s is already valid.

Example 3:

Input: s = ")", locked = "0"
Output: false
Explanation: locked permits us to change s[0]. 
Changing s[0] to either '(' or ')' will not make s valid.

Constraints:

n == s.length == locked.length
1 <= n <= 10⁵
s[i] is either '(' or ')'.
locked[i] is either '0' or '1'.

Asked at 7 companies

Moloco ServiceNow

IBM Amazon

Google Meta Bloomberg

Topics

Hints open one at a time

Hint 1

Can an odd length string ever be valid?

Hint 2

From left to right, if a locked ')' is encountered, it must be balanced with either a locked '(' or an unlocked index on its left. If neither exist, what conclusion can be drawn? If both exist, which one is more preferable to use?

Hint 3

After the above, we may have locked indices of '(' and additional unlocked indices. How can you balance out the locked '(' now? What if you cannot balance any locked '('?

20:41

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution