leetcode

// 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));
}