2564. Substring XOR Queries
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 of 5, and 5 ^ 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 of 1, and 1 ^ 4 = 5. So, the answer is [0,0].
Constraints:
1 <= s.length <= 104
s[i]
is either'0'
or'1'
.1 <= queries.length <= 105
0 <= 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 \times \log M + m)$, and the space complexity is $O(n \times \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 $2^{31} - 1$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
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 |
|
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 |
|