Check if a Parentheses String Can Be Valid LeetCode solution in C++

1
class Solution {
2
 public:
3
  bool canBeValid(string s, string locked) {
4
    int n = s.size();
5
    if (n & 1) return false;
6

7
    int balance = 0;
8

9
    // First check balance from left to right
10
    // For opening '(' brackets
11

12
    for (int i = 0; i < n; i++) {
13
      // If either char is ( or it is unlocked,
14
      // We can increment balance
15

16
      if (locked[i] == '0' || s[i] == '(')
17
        balance++;
18
      else
19
        balance--; // otherwise decrement balance, since it is ) and also locked
20

21
      // Since balance is negative, we have more ')'.
22
      // And there is no unlocked char available
23
      // SO, it is invalid string for sure
24

25
      if (balance < 0) return false;
26
    }
27

28
    // reset balance
29
    balance = 0;
30

31
    // Then also check balance from right to left
32
    // For closing ')' brackets
33

34
    for (int i = n - 1; i >= 0; i--) {
35
      // If either char is ) or it is unlocked,
36
      // We can increment balance
37

38
      if (locked[i] == '0' || s[i] == ')')
39
        balance++;
40
      else
41
        balance--;
42

43
      // Since balance is negative, we have more '('.
44
      // And there is no unlocked char available
45
      // SO, it is invalid string for sure
46

47
      if (balance < 0) return false;
48
    }
49

50
    return true;
51
  }
52
};