921. Minimum Add to Make Parentheses Valid
Difficulty: Medium
Topics: String, Stack, Greedy
A parentheses string is valid if and only if:
- It is the empty string,
- It can be written as AB (A concatenated with B), where A and B are valid strings, or
- It can be written as (A), where A is a valid string.
You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.
- For example, if s = "()))", you can insert an opening parenthesis to be "(()))" or a closing parenthesis to be "())))".
Return the minimum number of moves required to make s valid.
Example 1:
- Input: s = "())"
- Output: 1
Example 2:
- Input: s = "((("
- Output: 3
Constraints:
- 1
- s[i] is either '(' or ')'.
Solution:
We need to determine how many opening or closing parentheses need to be added to make the input string s valid. A valid string means that every opening parenthesis '(' has a corresponding closing parenthesis ')'.
We can solve this problem using a simple counter approach:
- We use a variable balance to keep track of the current balance between opening and closing parentheses.
- We use another variable additions to count the minimum number of parentheses required.
Approach:
- Loop through each character of the string s.
- If the character is '(', increment balance by 1.
- If the character is ')', decrement balance by 1:
- If balance becomes negative, it means there are more closing parentheses than opening ones. We need to add an opening parenthesis to balance it, so increment additions by 1 and reset balance to 0.
- At the end of the loop, if balance is greater than 0, it indicates there are unmatched opening parentheses, so add balance to additions.
Let's implement this solution in PHP: 921. Minimum Add to Make Parentheses Valid
<?php /** * @param String $s * @return Integer */ function minAddToMakeValid($s) { ... ... ... /** * go to ./solution.php */ } // Example usage: $s1 = "())"; echo minAddToMakeValid($s1); // Output: 1 $s2 = "((("; echo minAddToMakeValid($s2); // Output: 3 ?>
Explanation:
- For the string s = "())":
- balance becomes negative when the second ')' is encountered, so additions is incremented.
- At the end, balance is 0, and additions is 1, so we need 1 addition to make the string valid.
- For the string s = "(((":
- balance becomes 3 because there are 3 unmatched '(' at the end.
- The result is additions balance, which is 0 3 = 3.
This solution has a time complexity of O(n) where n is the length of the string, and a space complexity of O(1) since we only use a few variables.
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 . Minimum Add to Make Parentheses 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

Following its high-profile acquisition by Facebook in 2012, Instagram adopted two sets of APIs for third-party use. These are the Instagram Graph API and the Instagram Basic Display API.As a developer building an app that requires information from 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


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

SublimeText3 Linux new version
SublimeText3 Linux latest version

EditPlus Chinese cracked version
Small size, syntax highlighting, does not support code prompt function

SublimeText3 Chinese version
Chinese version, very easy to use

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

Dreamweaver Mac version
Visual web development tools
