921. Minimum Add to Make Parentheses Valid
https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/
Space - O(1)
---
Given a string
S of '(' and ')' parentheses, we add the minimum number of parentheses ( '(' or ')', and in any positions ) so that the resulting parentheses string is valid.
Formally, a parentheses string is valid if and only if:
- It is the empty string, or
- It can be written as
AB(Aconcatenated withB), whereAandBare valid strings, or - It can be written as
(A), whereAis a valid string.
Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.
Example 1:
Input: "())" Output: 1
Example 2:
Input: "(((" Output: 3
Example 3:
Input: "()" Output: 0
Example 4:
Input: "()))((" Output: 4
Note:
S.length <= 1000Sonly consists of'('and')'characters.
----
Time - O(N)Space - O(1)
---
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public int minAddToMakeValid(String S) { | |
| int open = 0, close = 0; | |
| for (int i = 0; i < S.length(); i++) { | |
| if (S.charAt(i) == '(') { | |
| open++; | |
| } else { | |
| if (open > 0) { | |
| open--; | |
| } else { | |
| close++; | |
| } | |
| } | |
| } | |
| return open + close; | |
| } | |
| } |
