921. Minimum Add to Make Parentheses Valid
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.length <= 1000
s[i] is either '(' or ')'.
https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/
Video coming soon!
Subscribe for more updates
Code Snippet
package com.ideserve.sakshi.questions;
/**
* <b>IDeserve <br>
* <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
* Minimum Add to Make Parentheses Valid
*
* @author Sakshi
*/
class Solution {
// Consider all kind of strings like '(()', ')))((('
public int minAddToMakeValid(String s) {
int n = s.length();
int openMinusClose = 0;
int closeMinusOpen = 0;
int i = 0;
while (i < n) {
if (s.charAt(i) == '(') {
openMinusClose++;
} else if (openMinusClose > 0 && s.charAt(i) == ')') {
openMinusClose--;
} else if (s.charAt(i) == ')') {
closeMinusOpen++;
}
i++;
}
return openMinusClose + closeMinusOpen;
}
}
Order of the Algorithm
Time Complexity is O(n)
Space Complexity is O(1)
Contribution
-
Sincere thanks from IDeserve community to Sakshi Kataria for compiling current post.
Sakshi Kataria