Problem Statement:
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.
- For example, if s = “()))”, you can insert an opening parenthesis to be “(()))” or a closing parenthesis to be “())))”.
You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.
Return the minimum number of moves required to make s valid.
Examples:
Example 1:
Input: s = “())”
Output: 1
Example 2:
Input: s = “(((“
Output: 3
Constraints
1 <= s.length <= 1000
s[i] is either '(' or ')'.
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(1)
Approach
- Use two variables:
openCount→ tracks unmatched'('moves→ tracks extra')'that need fixing
- Traverse the string:
- If
'('→ increment openCount - If
')':- If
openCount > 0→ match it(openCount--) - Else → it's invalid → increment
moves
- If
- At the end, Add remaining unmatched
'('(openCount)tomoves
Dry Run
Input: s = "())("
Initial:
openCount = 0
moves = 0
Step 1: c = '('
openCount++ → openCount = 1
moves = 0
Step 2: c = ')'
openCount > 0 → openCount--
openCount = 0
moves = 0
Step 3: c = ')'
openCount == 0 → moves++
openCount = 0
moves = 1
Step 4: c = '('
openCount++ → openCount = 1
moves = 1
End of loop:
openCount = 1 (unmatched '(')
moves = 1 (extra ')')
Result:
return moves + openCount = 1 + 1 = 2
Output: 2
var minAddToMakeValid = function(s) {
let openCount = 0, moves = 0;
for (let c of s) {
if (c == "(") {
openCount++;
} else {
if (openCount == 0) {
moves++;
} else {
openCount--; // FIXED
}
}
}
return moves + openCount;
};
def minAddToMakeValid(s: str) -> int:
openCount = 0
moves = 0
for c in s:
if c == '(':
openCount += 1
else:
if openCount == 0:
moves += 1
else:
openCount -= 1
return moves + openCount
class Solution {
public int minAddToMakeValid(String s) {
int openCount = 0, moves = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
openCount++;
} else {
if (openCount == 0) {
moves++;
} else {
openCount--;
}
}
}
return moves + openCount;
}
}
class Solution {
public:
int minAddToMakeValid(string s) {
int openCount = 0, moves = 0;
for (char c : s) {
if (c == '(') {
openCount++;
} else {
if (openCount == 0) {
moves++;
} else {
openCount--;
}
}
}
return moves + openCount;
}
};
#include <stdio.h>
int minAddToMakeValid(char* s) {
int openCount = 0, moves = 0;
for (int i = 0; s[i] != '\0'; i++) {
if (s[i] == '(') {
openCount++;
} else {
if (openCount == 0) {
moves++;
} else {
openCount--;
}
}
}
return moves + openCount;
}
public class Solution {
public int MinAddToMakeValid(string s) {
int openCount = 0, moves = 0;
foreach (char c in s) {
if (c == '(') {
openCount++;
} else {
if (openCount == 0) {
moves++;
} else {
openCount--;
}
}
}
return moves + openCount;
}
}
