Skip to content

2116. Check if a Parentheses String Can Be Valid 👍

  • Time: $O(n)$
  • Space: $O(n)$
 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
class Solution {
 public:
  bool canBeValid(string s, string locked) {
    if (s.length() % 2 == 1)
      return false;

    const bool leftToRightIsOkay = check(s, locked, true);
    ranges::reverse(s);
    ranges::reverse(locked);
    const bool rightToLeftIsOkay = check(s, locked, false);
    return leftToRightIsOkay && rightToLeftIsOkay;
  }

 private:
  bool check(const string& s, const string& locked, bool isForward) {
    int changeable = 0;
    int l = 0;
    int r = 0;

    for (int i = 0; i < s.length(); ++i) {
      const char c = s[i];
      const char lock = locked[i];
      if (lock == '0')
        ++changeable;
      else if (c == '(')
        ++l;
      else  // c == ')'
        ++r;
      if (isForward && changeable + l - r < 0)
        return false;
      if (!isForward && changeable + r - l < 0)
        return false;
    }

    return true;
  }
};

 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
class Solution {
  public boolean canBeValid(String s, String locked) {
    if (s.length() % 2 == 1)
      return false;

    return check(s, locked, true) && check(new StringBuilder(s).reverse().toString(),
                                           new StringBuilder(locked).reverse().toString(), false);
  }

  private boolean check(final String s, final String locked, boolean isForward) {
    int changeable = 0;
    int l = 0;
    int r = 0;

    for (int i = 0; i < s.length(); ++i) {
      final char c = s.charAt(i);
      final char lock = locked.charAt(i);
      if (lock == '0')
        ++changeable;
      else if (c == '(')
        ++l;
      else // c == ')'
        ++r;
      if (isForward && changeable + l - r < 0)
        return false;
      if (!isForward && changeable + r - l < 0)
        return false;
    }

    return true;
  }
}

 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
class Solution:
  def canBeValid(self, s: str, locked: str) -> bool:
    if len(s) % 2 == 1:
      return False

    def check(s: str, locked: str, isForward: bool) -> bool:
      changeable = 0
      l = 0
      r = 0

      for c, lock in zip(s, locked):
        if lock == '0':
          changeable += 1
        elif c == '(':
          l += 1
        else:  # c == ')'
          r += 1
        if isForward and changeable + l - r < 0:
          return False
        if not isForward and changeable + r - l < 0:
          return False

      return True

    return check(s, locked, True) and check(s[::-1], locked[::-1], False)