Welcome to Subscribe On Youtube

2116. Check if a Parentheses String Can Be Valid

Description

A parentheses string is a non-empty string consisting only of '(' and ')'. It is valid if any of the following conditions is true:

• It is ().
• It can be written as AB (A concatenated with B), where A and B are valid parentheses strings.
• It can be written as (A), where A is a valid parentheses string.

You are given a parentheses string s and a string locked, both of length n. locked is a binary string consisting only of '0's and '1's. For each index i of locked,

• If locked[i] is '1', you cannot change s[i].
• But if locked[i] is '0', you can change s[i] to either '(' or ')'.

Return true if you can make s a valid parentheses string. Otherwise, return false.

 

Example 1:

Input: s = "))()))", locked = "010100"
Output: true
Explanation: locked[1] == '1' and locked[3] == '1', so we cannot change s[1] or s[3].
We change s[0] and s[4] to '(' while leaving s[2] and s[5] unchanged to make s valid.

Example 2:

Input: s = "()()", locked = "0000"
Output: true
Explanation: We do not need to make any changes because s is already valid.

Example 3:

Input: s = ")", locked = "0"
Output: false
Explanation: locked permits us to change s[0]. 
Changing s[0] to either '(' or ')' will not make s valid.

 

Constraints:

• n == s.length == locked.length
• 1 <= n <= 105
• s[i] is either '(' or ')'.
• locked[i] is either '0' or '1'.

Solutions

• Java
• C++
• Python
• Go

• class Solution {
      public boolean canBeValid(String s, String locked) {
          int n = s.length();
          if (n % 2 == 1) {
              return false;
          }
          int x = 0;
          for (int i = 0; i < n; ++i) {
              if (s.charAt(i) == '(' || locked.charAt(i) == '0') {
                  ++x;
              } else if (x > 0) {
                  --x;
              } else {
                  return false;
              }
          }
          x = 0;
          for (int i = n - 1; i >= 0; --i) {
              if (s.charAt(i) == ')' || locked.charAt(i) == '0') {
                  ++x;
              } else if (x > 0) {
                  --x;
              } else {
                  return false;
              }
          }
          return true;
      }
  }
  

• class Solution {
  public:
      bool canBeValid(string s, string locked) {
          int n = s.size();
          if (n & 1) {
              return false;
          }
          int x = 0;
          for (int i = 0; i < n; ++i) {
              if (s[i] == '(' || locked[i] == '0') {
                  ++x;
              } else if (x) {
                  --x;
              } else {
                  return false;
              }
          }
          x = 0;
          for (int i = n - 1; i >= 0; --i) {
              if (s[i] == ')' || locked[i] == '0') {
                  ++x;
              } else if (x) {
                  --x;
              } else {
                  return false;
              }
          }
          return true;
      }
  };
  

• class Solution:
      def canBeValid(self, s: str, locked: str) -> bool:
          n = len(s)
          if n & 1:
              return False
          x = 0
          for i in range(n):
              if s[i] == '(' or locked[i] == '0':
                  x += 1
              elif x:
                  x -= 1
              else:
                  return False
          x = 0
          for i in range(n - 1, -1, -1):
              if s[i] == ')' or locked[i] == '0':
                  x += 1
              elif x:
                  x -= 1
              else:
                  return False
          return True
  
  

• func canBeValid(s string, locked string) bool {
  	n := len(s)
  	if n%2 == 1 {
  		return false
  	}
  	x := 0
  	for i := range s {
  		if s[i] == '(' || locked[i] == '0' {
  			x++
  		} else if x > 0 {
  			x--
  		} else {
  			return false
  		}
  	}
  	x = 0
  	for i := n - 1; i >= 0; i-- {
  		if s[i] == ')' || locked[i] == '0' {
  			x++
  		} else if x > 0 {
  			x--
  		} else {
  			return false
  		}
  	}
  	return true
  }
  

All Problems

All Solutions