2116. Check if a Parentheses String Can Be Valid
Difficulty: Medium
Topics: String, Stack, Greedy
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 5
- s[i] is either '(' or ')'.
- locked[i] is either '0' or '1'.
Hint:
- Can an odd length string ever be valid?
- 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?
- 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 '('?
Solution:
We can approach it step by step, keeping in mind the constraints and the behavior of the locked positions.
Key Points:
- If the length of the string is odd, we can immediately return false because a valid parentheses string must have an even length (each opening ( needs a closing )).
- We need to keep track of the number of open parentheses (() and closed parentheses ()) as we iterate through the string. If at any point the number of closing parentheses exceeds the number of opening ones, it's impossible to balance the string and we return false.
- We must carefully handle the positions that are locked (locked[i] == '1') and unlocked (locked[i] == '0'). Unlocked positions allow us to change the character, but locked positions do not.
Algorithm:
- Step 1: Check if the length of the string s is odd. If so, return false immediately.
-
Step 2: Loop through the string from left to right to track the balance of parentheses.
- Use a counter to track the balance between opening ( and closing ) parentheses.
- If at any point, the number of closing parentheses exceeds the opening parentheses, check if the locked positions have enough flexibility to balance it.
- After processing the entire string, check if the parentheses are balanced, i.e., if there are no leftover unmatched opening parentheses.
Let's implement this solution in PHP: 2116. Check if a Parentheses String Can Be Valid
<?php /** * @param String $s * @param String $locked * @return Boolean */ function canBeValid($s, $locked) { ... ... ... /** * go to ./solution.php */ } // Example usage: $s = "))()))"; $locked = "010100"; var_dump(canBeValid($s, $locked)); // Output: bool(true) $s = "()()"; $locked = "0000"; var_dump(canBeValid($s, $locked)); // Output: bool(true) $s = ")"; $locked = "0"; var_dump(canBeValid($s, $locked)); // Output: bool(false) ?>
Explanation:
-
First pass (left to right):
- We iterate through the string and track the balance of open parentheses. Each time we encounter an open parenthesis (, we increment the open counter. For a closed parenthesis ), we decrement the open counter.
- If the current character is unlocked (locked[i] == '0'), we can assume it to be ( if needed to balance the parentheses.
- If at any point the open counter goes negative, it means we have more closing parentheses than opening ones, and we return false.
-
Second pass (right to left):
- We perform a similar operation in reverse to handle the scenario of unmatched opening parentheses that might be at the end of the string.
- Here we track closing parentheses ()) with the close counter and ensure that no unbalanced parentheses exist.
Edge Case: If the string length is odd, we immediately return false because it cannot form a valid parentheses string.
Time Complexity:
- Both passes (left-to-right and right-to-left) take linear time, O(n), where n is the length of the string. Thus, the overall time complexity is O(n), which is efficient for the input size constraints.
This solution correctly handles the problem within the given constraints.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
- GitHub
The above is the detailed content of Check if a Parentheses String Can Be Valid. For more information, please follow other related articles on the PHP Chinese website!

Long URLs, often cluttered with keywords and tracking parameters, can deter visitors. A URL shortening script offers a solution, creating concise links ideal for social media and other platforms. These scripts are valuable for individual websites a

Laravel simplifies handling temporary session data using its intuitive flash methods. This is perfect for displaying brief messages, alerts, or notifications within your application. Data persists only for the subsequent request by default: $request-

This is the second and final part of the series on building a React application with a Laravel back-end. In the first part of the series, we created a RESTful API using Laravel for a basic product-listing application. In this tutorial, we will be dev

Laravel provides concise HTTP response simulation syntax, simplifying HTTP interaction testing. This approach significantly reduces code redundancy while making your test simulation more intuitive. The basic implementation provides a variety of response type shortcuts: use Illuminate\Support\Facades\Http; Http::fake([ 'google.com' => 'Hello World', 'github.com' => ['foo' => 'bar'], 'forge.laravel.com' =>

The PHP Client URL (cURL) extension is a powerful tool for developers, enabling seamless interaction with remote servers and REST APIs. By leveraging libcurl, a well-respected multi-protocol file transfer library, PHP cURL facilitates efficient execution of various network protocols, including HTTP, HTTPS, and FTP. This extension offers granular control over HTTP requests, supports multiple concurrent operations, and provides built-in security features.

Do you want to provide real-time, instant solutions to your customers' most pressing problems? Live chat lets you have real-time conversations with customers and resolve their problems instantly. It allows you to provide faster service to your custom

The 2025 PHP Landscape Survey investigates current PHP development trends. It explores framework usage, deployment methods, and challenges, aiming to provide insights for developers and businesses. The survey anticipates growth in modern PHP versio

In this article, we're going to explore the notification system in the Laravel web framework. The notification system in Laravel allows you to send notifications to users over different channels. Today, we'll discuss how you can send notifications ov


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

AI Hentai Generator
Generate AI Hentai for free.

Hot Article

Hot Tools

Safe Exam Browser
Safe Exam Browser is a secure browser environment for taking online exams securely. This software turns any computer into a secure workstation. It controls access to any utility and prevents students from using unauthorized resources.

SublimeText3 Linux new version
SublimeText3 Linux latest version

SublimeText3 Chinese version
Chinese version, very easy to use

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Mac version
God-level code editing software (SublimeText3)
