Description
You are given a binary string s, and a 2D integer array queries where queries[i] = [firsti, secondi].
For the ith query, find the shortest substring of s whose decimal value, val, yields secondi when bitwise XORed with firsti. In other words, val ^ firsti == secondi.
The answer to the ith query is the endpoints (0-indexed) of the substring [lefti, righti] or [-1, -1] if no such substring exists. If there are multiple answers, choose the one with the minimum lefti.
Return an array ans where ans[i] = [lefti, righti] is the answer to the ith query.
A substring is a contiguous non-empty sequence of characters within a string.
Example 1:
Input: s = "101101", queries = [[0,5],[1,2]] Output: [[0,2],[2,3]] Explanation: For the first query the substring in range[0,2]is "101" which has a decimal value of5, and5 ^ 0 = 5, hence the answer to the first query is[0,2]. In the second query, the substring in range[2,3]is "11", and has a decimal value of 3, and 3^ 1 = 2. So,[2,3]is returned for the second query.
Example 2:
Input: s = "0101", queries = [[12,8]]
Output: [[-1,-1]]
Explanation: In this example there is no substring that answers the query, hence [-1,-1] is returned.
Example 3:
Input: s = "1", queries = [[4,5]] Output: [[0,0]] Explanation: For this example, the substring in range[0,0]has a decimal value of1, and1 ^ 4 = 5. So, the answer is[0,0].
Constraints:
1 <= s.length <= 104s[i]is either'0'or'1'.1 <= queries.length <= 1050 <= firsti, secondi <= 109
Solutions
Solution 1: Preprocessing + Enumeration
We can first preprocess all substrings of length 1 to 32 into their corresponding decimal values, find the minimum index and the corresponding right endpoint index for each value, and store them in the hash table d.
Then we enumerate each query. For each query [first, second], we only need to check in the hash table d whether there exists a key-value pair with the key as first \oplus second. If it exists, add the corresponding minimum index and right endpoint index to the answer array. Otherwise, add [-1, -1].
The time complexity is O(n × log M + m), and the space complexity is O(n × log M). Where n and m are the lengths of the string s and the query array queries respectively, and M can take the maximum value of an integer 231 - 1.
class Solution: def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]: d = {} n = len(s) for i in range(n): x = 0 for j in range(32): if i + j >= n: break x = x << 1 | int(s[i + j]) if x not in d: d[x] = [i, i + j] if x == 0: break return [d.get(first ^ second, [-1, -1]) for first, second in queries](code-box)
