rustgym/leetcode/
_1541_minimum_insertions_to_balance_a_parentheses_string.rs

1struct Solution;
2
3impl Solution {
4    fn min_insertions(s: String) -> i32 {
5        let mut right = 0;
6        let mut res = 0;
7        for c in s.chars().rev() {
8            if c == ')' {
9                right += 1;
10            } else {
11                if right >= 2 {
12                    right -= 2;
13                    if right % 2 == 1 {
14                        right += 1;
15                        res += 1;
16                    }
17                } else {
18                    if right == 0 {
19                        res += 2;
20                    } else {
21                        res += 1;
22                        right -= 1;
23                    }
24                }
25            }
26        }
27        res += right / 2 + (right % 2) * 2;
28        res
29    }
30}
31
32#[test]
33fn test() {
34    let s = "())".to_string();
35    let res = 0;
36    assert_eq!(Solution::min_insertions(s), res);
37    let s = "))())(".to_string();
38    let res = 3;
39    assert_eq!(Solution::min_insertions(s), res);
40    let s = "((((((".to_string();
41    let res = 12;
42    assert_eq!(Solution::min_insertions(s), res);
43    let s = ")))))))".to_string();
44    let res = 5;
45    assert_eq!(Solution::min_insertions(s), res);
46    let s = "(()))(()))()())))".to_string();
47    let res = 4;
48    assert_eq!(Solution::min_insertions(s), res);
49}