2024-12-24
3203. Find Minimum Diameter After Merging Two Trees

Topic: Tree, Depth-First Search, Breadth-First Search, Graph
Difficulty: Hard

Problem:
There exist two undirected trees with n and m nodes, numbered from 0 to n - 1 and from 0 to m - 1, respectively. You are given two 2D integer arrays edges1 and edges2 of lengths n - 1 and m - 1, respectively, where edges1[i] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i in the first tree and edges2[i] = [u_i, v_i] indicates that there is an edge between nodes u_i and v_i in the second tree.

You must connect one node from the first tree with another node from the second tree with an edge.

Return the minimum possible diameter of the resulting tree.

The diameter of a tree is the length of the longest path between any two nodes in the tree.

Example 1:
Image: https://assets.leetcode.com/uploads/2024/04/22/example11-transformed.png

Input: edges1 = [0,1,0,2,0,3], edges2 = [0,1]

Output: 3

Explanation:

We can obtain a tree of diameter 3 by connecting node 0 from the first tree with any node from the second tree.

Example 2:

Image: https://assets.leetcode.com/uploads/2024/04/22/example211.png

Input: edges1 = [0,1,0,2,0,3,2,4,2,5,3,6,2,7], edges2 = [0,1,0,2,0,3,2,4,2,5,3,6,2,7]

Output: 5

Explanation:

We can obtain a tree of diameter 5 by connecting node 0 from the first tree with node 0 from the second tree.

Constraints:

• 1 <= n, m <= 10^5
• edges1.length == n - 1
• edges2.length == m - 1
• edges1[i].length == edges2[i].length == 2
• edges1[i] = [a_i, b_i]
• 0 <= a_i, b_i < n
• edges2[i] = [u_i, v_i]
• 0 <= u_i, v_i < m
• The input is generated such that edges1 and edges2 represent valid trees.

2024-12-25
515. Find Largest Value in Each Tree Row

Topic: Tree, Depth-First Search, Breadth-First Search, Binary Tree
Difficulty: Medium

Problem:
Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).

Example 1:

Image: https://assets.leetcode.com/uploads/2020/08/21/largest_e1.jpg

Input: root = [1,3,2,5,3,null,9]
Output: [1,3,9]

Example 2:

Input: root = [1,2,3]
Output: [1,3]

Constraints:

• The number of nodes in the tree will be in the range [0, 10^4].
• -2^31 <= Node.val <= 2^31 - 1

2024-12-26
494. Target Sum

Topic: Array, Dynamic Programming, Backtracking
Difficulty: Medium

Problem:
You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

• For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".

Return the number of different expressions that you can build, which evaluates to target.

Example 1:

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

Example 2:

Input: nums = [1], target = 1
Output: 1

Constraints:

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

2024-12-27
1014. Best Sightseeing Pair

Topic: Array, Dynamic Programming
Difficulty: Medium

Problem:
You are given an integer array values where valuesi represents the value of the i^th sightseeing spot. Two sightseeing spots i and j have a distance j - i between them.

The score of a pair (i < j) of sightseeing spots is values[i] + values[j] + i - j: the sum of the values of the sightseeing spots, minus the distance between them.

Return the maximum score of a pair of sightseeing spots.

Example 1:

Input: values = [8,1,5,2,6]
Output: 11
Explanation: i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11

Example 2:

Input: values = [1,2]
Output: 2

Constraints:

• 2 <= values.length <= 5 * 10^4
• 1 <= values[i] <= 1000

2024-12-28
689. Maximum Sum of 3 Non-Overlapping Subarrays

Topic: Array, Dynamic Programming
Difficulty: Hard

Problem:
Given an integer array nums and an integer k, find three non-overlapping subarrays of length k with maximum sum and return them.

Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.

Example 1:

Input: nums = [1,2,1,2,6,7,5,1], k = 2
Output: [0,3,5]
Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.

Example 2:

Input: nums = [1,2,1,2,1,2,1,2,1], k = 2
Output: [0,2,4]

Constraints:

• 1 <= nums.length <= 2 * 10^4
• 1 <= nums[i] < 2^16
• 1 <= k <= floor(nums.length / 3)

2024-12-29
1639. Number of Ways to Form a Target String Given a Dictionary

Topic: Array, String, Dynamic Programming
Difficulty: Hard

Problem:
You are given a list of strings of the same length words and a string target.

Your task is to form target using the given words under the following rules:

• target should be formed from left to right.
• To form the i^th character (0-indexed) of target, you can choose the k^th character of the j^th string in words if target[i] = words[j][k].
• Once you use the k^th character of the j^th string of words, you can no longer use the x^th character of any string in words where x <= k. In other words, all characters to the left of or at index k become unusuable for every string.
• Repeat the process until you form the string target.

Notice that you can use multiple characters from the same string in words provided the conditions above are met.

Return the number of ways to form target from words. Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: words = ["acca","bbbb","caca"], target = "aba"
Output: 6
Explanation: There are 6 ways to form target.
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("acca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("caca")

Example 2:

Input: words = ["abba","baab"], target = "bab"
Output: 4
Explanation: There are 4 ways to form target.
"bab" -> index 0 ("baab"), index 1 ("baab"), index 2 ("abba")
"bab" -> index 0 ("baab"), index 1 ("baab"), index 3 ("baab")
"bab" -> index 0 ("baab"), index 2 ("baab"), index 3 ("baab")
"bab" -> index 1 ("abba"), index 2 ("baab"), index 3 ("baab")

Constraints:

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• All strings in words have the same length.
• 1 <= target.length <= 1000
• words[i] and target contain only lowercase English letters.

2024-12-30
2466. Count Ways To Build Good Strings

Topic: Dynamic Programming
Difficulty: Medium

Problem:
Given the integers zero, one, low, and high, we can construct a string by starting with an empty string, and then at each step perform either of the following:

• Append the character '0' zero times.
• Append the character '1' one times.

This can be performed any number of times.

A good string is a string constructed by the above process having a length between low and high (inclusive).

Return the number of different good strings that can be constructed satisfying these properties. Since the answer can be large, return it modulo 10^9 + 7.

Example 1:

Input: low = 3, high = 3, zero = 1, one = 1
Output: 8
Explanation: 
One possible valid good string is "011". 
It can be constructed as follows: "" -> "0" -> "01" -> "011". 
All binary strings from "000" to "111" are good strings in this example.

Example 2:

Input: low = 2, high = 3, zero = 1, one = 2
Output: 5
Explanation: The good strings are "00", "11", "000", "110", and "011".

Constraints:

• 1 <= low <= high <= 10^5
• 1 <= zero, one <= low

2024-12-31
983. Minimum Cost For Tickets

Topic: Array, Dynamic Programming
Difficulty: Medium

Problem:
You have planned some train traveling one year in advance. The days of the year in which you will travel are given as an integer array days. Each day is an integer from 1 to 365.

Train tickets are sold in three different ways:

• a 1-day pass is sold for costs[0] dollars,
• a 7-day pass is sold for costs[1] dollars, and
• a 30-day pass is sold for costs[2] dollars.

The passes allow that many days of consecutive travel.

• For example, if we get a 7-day pass on day 2, then we can travel for 7 days: 2, 3, 4, 5, 6, 7, and 8.

Return the minimum number of dollars you need to travel every day in the given list of days.

Example 1:

Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total, you spent $11 and covered all the days of your travel.

Example 2:

Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
Output: 17
Explanation: For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 30-day pass for costs[2] = $15 which covered days 1, 2, ..., 30.
On day 31, you bought a 1-day pass for costs[0] = $2 which covered day 31.
In total, you spent $17 and covered all the days of your travel.

Constraints:

• 1 <= days.length <= 365
• 1 <= days[i] <= 365
• days is in strictly increasing order.
• costs.length == 3
• 1 <= costs[i] <= 1000

2025-01-01
1422. Maximum Score After Splitting a String

Topic: String, Prefix Sum
Difficulty: Easy

Problem:
Given a string s of zeros and ones, return the maximum score after splitting the string into two non-empty substrings (i.e. left substring and right substring).

The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring.

Example 1:

Input: s = "011101"
Output: 5 
Explanation: 
All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5 
left = "01" and right = "1101", score = 1 + 3 = 4 
left = "011" and right = "101", score = 1 + 2 = 3 
left = "0111" and right = "01", score = 1 + 1 = 2 
left = "01110" and right = "1", score = 2 + 1 = 3

Example 2:

Input: s = "00111"
Output: 5
Explanation: When left = "00" and right = "111", we get the maximum score = 2 + 3 = 5

Example 3:

Input: s = "1111"
Output: 3

Constraints:

• 2 <= s.length <= 500
• The string s consists of characters '0' and '1' only.

2025-01-02
2559. Count Vowel Strings in Ranges

Topic: Array, String, Prefix Sum
Difficulty: Medium

Problem:
You are given a 0-indexed array of strings words and a 2D array of integers queries.

Each query queries[i] = [l_i, r_i] asks us to find the number of strings present in the range l_i to r_i (both inclusive) of words that start and end with a vowel.

Return an array ans of size queries.length, where ans[i] is the answer to the i^th query.

Note that the vowel letters are 'a', 'e', 'i', 'o', and 'u'.

Example 1:

Input: words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]]
Output: [2,3,0]
Explanation: The strings starting and ending with a vowel are "aba", "ece", "aa" and "e".
The answer to the query [0,2] is 2 (strings "aba" and "ece").
to query [1,4] is 3 (strings "ece", "aa", "e").
to query [1,1] is 0.
We return [2,3,0].

Example 2:

Input: words = ["a","e","i"], queries = [[0,2],[0,1],[2,2]]
Output: [3,2,1]
Explanation: Every string satisfies the conditions, so we return [3,2,1].

Constraints:

• 1 <= words.length <= 10^5
• 1 <= words[i].length <= 40
• words[i] consists only of lowercase English letters.
• sum(words[i].length) <= 3 * 10^5
• 1 <= queries.length <= 10^5
• 0 <= l_i <= r_i < words.length

2025-01-03
2270. Number of Ways to Split Array

Topic: Array, Prefix Sum
Difficulty: Medium

Problem:
You are given a 0-indexed integer array nums of length n.

nums contains a valid split at index i if the following are true:

• The sum of the first i + 1 elements is greater than or equal to the sum of the last n - i - 1 elements.
• There is at least one element to the right of i. That is, 0 <= i < n - 1.

Return the number of valid splits in nums.

Example 1:

Input: nums = [10,4,-8,7]
Output: 2
Explanation: 
There are three ways of splitting nums into two non-empty parts:
- Split nums at index 0. Then, the first part is [10], and its sum is 10. The second part is [4,-8,7], and its sum is 3. Since 10 >= 3, i = 0 is a valid split.
- Split nums at index 1. Then, the first part is [10,4], and its sum is 14. The second part is [-8,7], and its sum is -1. Since 14 >= -1, i = 1 is a valid split.
- Split nums at index 2. Then, the first part is [10,4,-8], and its sum is 6. The second part is [7], and its sum is 7. Since 6 < 7, i = 2 is not a valid split.
Thus, the number of valid splits in nums is 2.

Example 2:

Input: nums = [2,3,1,0]
Output: 2
Explanation: 
There are two valid splits in nums:
- Split nums at index 1. Then, the first part is [2,3], and its sum is 5. The second part is [1,0], and its sum is 1. Since 5 >= 1, i = 1 is a valid split. 
- Split nums at index 2. Then, the first part is [2,3,1], and its sum is 6. The second part is [0], and its sum is 0. Since 6 >= 0, i = 2 is a valid split.

Constraints:

• 2 <= nums.length <= 10^5
• -10^5 <= nums[i] <= 10^5

2025-01-04
1930. Unique Length-3 Palindromic Subsequences

Topic: Hash Table, String, Bit Manipulation, Prefix Sum
Difficulty: Medium

Problem:
Given a string s, return the number of unique palindromes of length three that are a subsequence of s.

Note that even if there are multiple ways to obtain the same subsequence, it is still only counted once.

A palindrome is a string that reads the same forwards and backwards.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

Example 1:

Input: s = "aabca"
Output: 3
Explanation: The 3 palindromic subsequences of length 3 are:
- "aba" (subsequence of "aabca")
- "aaa" (subsequence of "aabca")
- "aca" (subsequence of "aabca")

Example 2:

Input: s = "adc"
Output: 0
Explanation: There are no palindromic subsequences of length 3 in "adc".

Example 3:

Input: s = "bbcbaba"
Output: 4
Explanation: The 4 palindromic subsequences of length 3 are:
- "bbb" (subsequence of "bbcbaba")
- "bcb" (subsequence of "bbcbaba")
- "bab" (subsequence of "bbcbaba")
- "aba" (subsequence of "bbcbaba")

Constraints:

• 3 <= s.length <= 10^5
• s consists of only lowercase English letters.

2025-01-05
2381. Shifting Letters II

Topic: Array, String, Prefix Sum
Difficulty: Medium

Problem:
You are given a string s of lowercase English letters and a 2D integer array shifts where shifts[i] = [start_i, end_i, direction_i]. For every i, shift the characters in s from the index start_i to the index end_i (inclusive) forward if direction_i = 1, or shift the characters backward if direction_i = 0.

Shifting a character forward means replacing it with the next letter in the alphabet (wrapping around so that 'z' becomes 'a'). Similarly, shifting a character backward means replacing it with the previous letter in the alphabet (wrapping around so that 'a' becomes 'z').

Return the final string after all such shifts to s are applied.

Example 1:

Input: s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]]
Output: "ace"
Explanation: Firstly, shift the characters from index 0 to index 1 backward. Now s = "zac".
Secondly, shift the characters from index 1 to index 2 forward. Now s = "zbd".
Finally, shift the characters from index 0 to index 2 forward. Now s = "ace".

Example 2:

Input: s = "dztz", shifts = [[0,0,0],[1,1,1]]
Output: "catz"
Explanation: Firstly, shift the characters from index 0 to index 0 backward. Now s = "cztz".
Finally, shift the characters from index 1 to index 1 forward. Now s = "catz".

Constraints:

• 1 <= s.length, shifts.length <= 5 * 10^4
• shifts[i].length == 3
• 0 <= start_i <= end_i < s.length
• 0 <= direction_i <= 1
• s consists of lowercase English letters.

2025-01-06
1769. Minimum Number of Operations to Move All Balls to Each Box

Topic: Array, String, Prefix Sum
Difficulty: Medium

Problem:
You have n boxes. You are given a binary string boxes of length n, where boxes[i] is '0' if the i^th box is empty, and '1' if it contains one ball.

In one operation, you can move one ball from a box to an adjacent box. Box i is adjacent to box j if abs(i - j) == 1. Note that after doing so, there may be more than one ball in some boxes.

Return an array answer of size n, where answer[i] is the minimum number of operations needed to move all the balls to the i^th box.

Each answer[i] is calculated considering the initial state of the boxes.

Example 1:

Input: boxes = "110"
Output: [1,1,3]
Explanation: The answer for each box is as follows:
1) First box: you will have to move one ball from the second box to the first box in one operation.
2) Second box: you will have to move one ball from the first box to the second box in one operation.
3) Third box: you will have to move one ball from the first box to the third box in two operations, and move one ball from the second box to the third box in one operation.

Example 2:

Input: boxes = "001011"
Output: [11,8,5,4,3,4]

Constraints:

• n == boxes.length
• 1 <= n <= 2000
• boxes[i] is either '0' or '1'.

2025-01-07
1408. String Matching in an Array

Topic: Array, String, String Matching
Difficulty: Easy

Problem:
Given an array of string words, return all strings in words that is a substring of another word. You can return the answer in any order.

A substring is a contiguous sequence of characters within a string

Example 1:

Input: words = ["mass","as","hero","superhero"]
Output: ["as","hero"]
Explanation: "as" is substring of "mass" and "hero" is substring of "superhero".
["hero","as"] is also a valid answer.

Example 2:

Input: words = ["leetcode","et","code"]
Output: ["et","code"]
Explanation: "et", "code" are substring of "leetcode".

Example 3:

Input: words = ["blue","green","bu"]
Output: []
Explanation: No string of words is substring of another string.

Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 30
• words[i] contains only lowercase English letters.
• All the strings of words are unique.

2025-01-08
3042. Count Prefix and Suffix Pairs I

Topic: Array, String, Trie, Rolling Hash, String Matching, Hash Function
Difficulty: Easy

Problem:
You are given a 0-indexed string array words.

Let's define a boolean function isPrefixAndSuffix that takes two strings, str1 and str2:

• isPrefixAndSuffix(str1, str2) returns true if str1 is both a prefix and a suffix of str2, and false otherwise.

For example, isPrefixAndSuffix("aba", "ababa") is true because "aba" is a prefix of "ababa" and also a suffix, but isPrefixAndSuffix("abc", "abcd") is false.

Return an integer denoting the number of index pairs (i, j) such that i < j, and isPrefixAndSuffix(words[i], words[j]) is true.

Example 1:

Input: words = ["a","aba","ababa","aa"]
Output: 4
Explanation: In this example, the counted index pairs are:
i = 0 and j = 1 because isPrefixAndSuffix("a", "aba") is true.
i = 0 and j = 2 because isPrefixAndSuffix("a", "ababa") is true.
i = 0 and j = 3 because isPrefixAndSuffix("a", "aa") is true.
i = 1 and j = 2 because isPrefixAndSuffix("aba", "ababa") is true.
Therefore, the answer is 4.

Example 2:

Input: words = ["pa","papa","ma","mama"]
Output: 2
Explanation: In this example, the counted index pairs are:
i = 0 and j = 1 because isPrefixAndSuffix("pa", "papa") is true.
i = 2 and j = 3 because isPrefixAndSuffix("ma", "mama") is true.
Therefore, the answer is 2.

Example 3:

Input: words = ["abab","ab"]
Output: 0
Explanation: In this example, the only valid index pair is i = 0 and j = 1, and isPrefixAndSuffix("abab", "ab") is false.
Therefore, the answer is 0.

Constraints:

• 1 <= words.length <= 50
• 1 <= words[i].length <= 10
• words[i] consists only of lowercase English letters.

2025-01-09
2185. Counting Words With a Given Prefix

Topic: Array, String, String Matching
Difficulty: Easy

Problem:
You are given an array of strings words and a string pref.

Return the number of strings in words that contain pref as a prefix.

A prefix of a string s is any leading contiguous substring of s.

Example 1:

Input: words = ["pay","attention","practice","attend"], pref = "at"
Output: 2
Explanation: The 2 strings that contain "at" as a prefix are: "attention" and "attend".

Example 2:

Input: words = ["leetcode","win","loops","success"], pref = "code"
Output: 0
Explanation: There are no strings that contain "code" as a prefix.

Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length, pref.length <= 100
• words[i] and pref consist of lowercase English letters.

2025-01-10
916. Word Subsets

Topic: Array, Hash Table, String
Difficulty: Medium

Problem:
You are given two string arrays words1 and words2.

A string b is a subset of string a if every letter in b occurs in a including multiplicity.

• For example, "wrr" is a subset of "warrior" but is not a subset of "world".

A string a from words1 is universal if for every string b in words2, b is a subset of a.

Return an array of all the universal strings in words1. You may return the answer in any order.

Example 1:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
Output: ["facebook","google","leetcode"]

Example 2:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["l","e"]
Output: ["apple","google","leetcode"]

Constraints:

• 1 <= words1.length, words2.length <= 10^4
• 1 <= words1[i].length, words2[i].length <= 10
• words1[i] and words2[i] consist only of lowercase English letters.
• All the strings of words1 are unique.

2025-01-11
1400. Construct K Palindrome Strings

Topic: Hash Table, String, Greedy, Counting
Difficulty: Medium

Problem:
Given a string s and an integer k, return true if you can use all the characters in s to construct k palindrome strings or false otherwise.

Example 1:

Input: s = "annabelle", k = 2
Output: true
Explanation: You can construct two palindromes using all characters in s.
Some possible constructions "anna" + "elble", "anbna" + "elle", "anellena" + "b"

Example 2:

Input: s = "leetcode", k = 3
Output: false
Explanation: It is impossible to construct 3 palindromes using all the characters of s.

Example 3:

Input: s = "true", k = 4
Output: true
Explanation: The only possible solution is to put each character in a separate string.

Constraints:

• 1 <= s.length <= 10^5
• s consists of lowercase English letters.
• 1 <= k <= 10^5

2025-01-12
2116. Check if a Parentheses String Can Be Valid

Topic: String, Stack, Greedy
Difficulty: Medium

Problem:
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:

Image: https://assets.leetcode.com/uploads/2021/11/06/eg1.png

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 <= 10^5
• s[i] is either '(' or ')'.
• locked[i] is either '0' or '1'.