Sponsored
Sponsored
This approach involves iterating through the string and using a balance counter to track the validity of the sequence.
We increment the balance for every opening parenthesis '(' and decrement it for a closing parenthesis ')'. If, at any point, the balance becomes negative, it means we have an extra closing parenthesis, and we need to increase the count of steps required to balance the string. By the end of the iteration, the balance will also tell us how many opening parentheses need to be closed to make the string valid.
Time Complexity: O(n) - We traverse the string once.
Space Complexity: O(1) - Only a few integer variables are used.
1using System;
2
3class Program {
4 public static int MinAddToMakeValid(string s) {
5 int balance = 0, result = 0;
6 foreach (char c in s) {
7 balance += (c == '(') ? 1 : -1;
8 if (balance == -1) {
9 result++;
10 balance++;
11 }
12 }
13 return result + balance;
14 }
15
16 static void Main() {
17 string s = ")((";
18 Console.WriteLine(MinAddToMakeValid(s));
19 }
20}The C# implementation employs similar logic within a foreach loop, adjusting balance and result based on each character.
In this approach, we leverage a stack structure to simulate parentheses placement, assisting in counting the balance.
Iterate over the string, pushing opening parentheses onto the stack and popping for each encountered closing parenthesis when possible. When a closing parenthesis finds no partner to pop, increase the invalid count, simulating the need for one more opening parenthesis. In the end, the stack length represents unmatched opening parentheses.
Time Complexity: O(n) - Iterate over the string once.
Space Complexity: O(1) - Uses a few integer counters.
#include <string>
int minAddToMakeValid(std::string s) {
int stack = 0, invalid = 0;
for (char ch : s) {
if (ch == '(') {
stack++;
} else {
if (stack > 0) {
stack--;
} else {
invalid++;
}
}
}
return invalid + stack;
}
int main() {
std::string s = ")(()";
std::cout << minAddToMakeValid(s) << std::endl;
return 0;
}This C++ solution emulates the stack logic with counters as described above.