Sponsored
Sponsored
This approach involves performing two passes over the string. In the first pass, traverse the string to identify unmatched closing parentheses and their indices. In the second pass, traverse from right to left to identify unmatched opening parentheses. This process allows removing these indices to yield a balanced parentheses string.
Time Complexity: O(n), where n is the length of the string, since each character is visited once in each pass.
Space Complexity: O(n), as we potentially have to store the valid portion of the string.
1#include <stdio.h>
2#include <string.h>
3#include <stdlib.h>
4
5char* minRemoveToMakeValid(char* s) {
6 int i, balance = 0, len = strlen(s);
7 char* result = (char*)malloc(len + 1);
8 char* builder = (char*)malloc(len + 1);
9 int j = 0;
10
11 // First pass: remove extra closing brackets
12 for (i = 0; i < len; ++i) {
13 if (s[i] == '(') {
14 balance++;
15 } else if (s[i] == ')') {
16 if (balance == 0) continue;
17 balance--;
18 }
19 builder[j++] = s[i];
20 }
21
22 builder[j] = '\0';
23 balance = 0;
24 j = 0;
25
26 // Second pass: remove extra opening brackets from the end
27 for (i = strlen(builder) - 1; i >= 0; --i) {
28 if (builder[i] == ')') {
29 balance++;
30 } else if (builder[i] == '(') {
31 if (balance == 0) continue;
32 balance--;
33 }
34 result[j++] = builder[i];
35 }
36 result[j] = '\0';
37
38 // Reverse the result to get final valid string
39 for (i = 0; i < j / 2; ++i) {
40 char tmp = result[i];
41 result[i] = result[j - i - 1];
42 result[j - i - 1] = tmp;
43 }
44
45 free(builder);
46 return result;
47}An array is used to filter out invalid closing parentheses on the first pass. The second pass corrects the string from the right by ignoring invalid opening parens, then reverses the string to final form.
This strategy employs a single-pass solution with a stack to track the indices of unmatched parentheses. Upon completing the pass, these tracked indices inform which characters can remain in the final valid string output. This approach saves memory by avoiding additional passes over the string.
Time Complexity: O(n), since each position in the strings is evaluated at most twice.
Space Complexity: O(n) for the indices stored during parentheses checking.
using System.Text;
using System.Collections.Generic;
public class Solution {
public string MinRemoveToMakeValid(string s) {
Stack<int> stack = new Stack<int>();
char[] arr = s.ToCharArray();
for (int i = 0; i < arr.Length; i++) {
if (arr[i] == '(') stack.Push(i);
else if (arr[i] == ')') {
if (stack.Count == 0) {
arr[i] = '*';
} else {
stack.Pop();
}
}
}
while (stack.Count > 0) {
arr[stack.Pop()] = '*';
}
StringBuilder sb = new StringBuilder();
foreach (char c in arr) {
if (c != '*') sb.Append(c);
}
return sb.ToString();
}
}C# aligns well with indexed string modification using array storage and stack operations, complementing the ported logic for consistent efficiency.