2116. Check if a Parentheses String Can Be Valid Medium

1/**
2 * [2116] Check if a Parentheses String Can Be Valid
3 *
4 * A parentheses string is a non-empty string consisting only of '(' and ')'. It is valid if any of the following conditions is true:
5 * 
6 * 	It is ().
7 * 	It can be written as AB (A concatenated with B), where A and B are valid parentheses strings.
8 * 	It can be written as (A), where A is a valid parentheses string.
9 * 
10 * 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,
11 * 
12 * 	If locked[i] is '1', you cannot change s[i].
13 * 	But if locked[i] is '0', you can change s[i] to either '(' or ')'.
14 * 
15 * Return true if you can make s a valid parentheses string. Otherwise, return false.
16 *  
17 * Example 1:
18 * <img alt="" src="https://assets.leetcode.com/uploads/2021/11/06/eg1.png" style="width: 311px; height: 101px;" />
19 * Input: s = "))()))", locked = "010100"
20 * Output: true
21 * Explanation: locked[1] == '1' and locked[3] == '1', so we cannot change s[1] or s[3].
22 * We change s[0] and s[4] to '(' while leaving s[2] and s[5] unchanged to make s valid.
23 * Example 2:
24 * 
25 * Input: s = "()()", locked = "0000"
26 * Output: true
27 * Explanation: We do not need to make any changes because s is already valid.
28 * 
29 * Example 3:
30 * 
31 * Input: s = ")", locked = "0"
32 * Output: false
33 * Explanation: locked permits us to change s[0]. 
34 * Changing s[0] to either '(' or ')' will not make s valid.
35 * 
36 *  
37 * Constraints:
38 * 
39 * 	n == s.length == locked.length
40 * 	1 <= n <= 10^5
41 * 	s[i] is either '(' or ')'.
42 * 	locked[i] is either '0' or '1'.
43 * 
44 */
45pub struct Solution {}
46
47// problem: https://leetcode.com/problems/check-if-a-parentheses-string-can-be-valid/
48// discuss: https://leetcode.com/problems/check-if-a-parentheses-string-can-be-valid/discuss/?currentPage=1&orderBy=most_votes&query=
49
50// submission codes start here
51
52impl Solution {
53    pub fn can_be_valid(s: String, locked: String) -> bool {
54        false
55    }
56}
57
58// submission codes end
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63
64    #[test]
65    fn test_2116() {
66    }
67}
68