aboutsummaryrefslogtreecommitdiff
path: root/min_remove_valid_parentheses.c
blob: 90300df581aa1082b091b836860d1bc5ecef7d50 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// 1249. Minimum Remove to Make Valid Parentheses
#include "leetcode.h"

/*
 * given a string s of '(' and ')' and lowercase english characters. your task
 * is to remove the minimum number of parentheses so that the resulting
 * parentheses string is valid and return any valid string. formally, a
 * parentheses string is valid if and only if it is the empty string, contains
 * only lowercase characters, or it can be written as AB where A and B are valid
 * strings, or it can be written as (A) where A is a valid string.
 */

char *minRemoveToMakeValid(char *s) {
  int n = strlen(s), size = 0, p = 0;
  bool *flag = calloc(n, sizeof(bool));
  int *stack = malloc(n * sizeof(int));
  for (int i = 0; i < n; i++) {
    if (s[i] == '(') {
      stack[size] = i;
      size++;
    }
    if (s[i] == ')') {
      if (size)
        size--;
      else
        flag[i] = 1;
    }
  }
  for (int i = 0; i < size; i++)
    flag[stack[i]] = 1;
  char *ans = malloc((n + 1) * sizeof(char));
  for (int i = 0; i < n; i++)
    if (!flag[i])
      ans[p] = s[i], p++;
  ans[p] = '\0';
  return ans;
}

int main() {
  char *s1 = "lee(t(c)o)de)", *s2 = "a)b(c)d", *s3 = "))((";
  printf("%s\n", minRemoveToMakeValid(s1));
  printf("%s\n", minRemoveToMakeValid(s2));
  printf("%s\n", minRemoveToMakeValid(s3));
}