aboutsummaryrefslogtreecommitdiff
path: root/min_add_make_parenthese_valid.c
blob: f0b2fe3193b7731dcd6b60f9d83b5de11af521d7 (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
// 921. Minimum Add to Make Parentheses Valid
#include "leetcode.h"

/*
 * a parentheses string is valid if and only if it is 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. you are given a parentheses
 * string 's'. in one move you can insert a parentheses at any position of the
 * string. return the minimum number of moves required to make 's' valid
 */

int minAddToMakeValid(char *s) {
  int open = 0, close = 0, n = strlen(s);
  for (int i = 0; i < n; i++)
    if (s[i] == '(')
      open++;
    else {
      if (open)
        open--;
      else
        close++;
    }
  return open + close;
}

int main() {
  char *s1 = "())", *s2 = "(((";
  printf("%d\n", minAddToMakeValid(s1)); // expect: 1
  printf("%d\n", minAddToMakeValid(s2)); // expect: 3
}