# 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$.

• class Solution {
public int[][] substringXorQueries(String s, int[][] queries) {
Map<Integer, int[]> d = new HashMap<>();
int n = s.length();
for (int i = 0; i < n; ++i) {
int x = 0;
for (int j = 0; j < 32 && i + j < n; ++j) {
x = x << 1 | (s.charAt(i + j) - '0');
d.putIfAbsent(x, new int[] {i, i + j});
if (x == 0) {
break;
}
}
}
int m = queries.length;
int[][] ans = new int[m][2];
for (int i = 0; i < m; ++i) {
int first = queries[i][0], second = queries[i][1];
int val = first ^ second;
ans[i] = d.getOrDefault(val, new int[] {-1, -1});
}
return ans;
}
}

• class Solution {
public:
vector<vector<int>> substringXorQueries(string s, vector<vector<int>>& queries) {
unordered_map<int, vector<int>> d;
int n = s.size();
for (int i = 0; i < n; ++i) {
int x = 0;
for (int j = 0; j < 32 && i + j < n; ++j) {
x = x << 1 | (s[i + j] - '0');
if (!d.count(x)) {
d[x] = {i, i + j};
}
if (x == 0) {
break;
}
}
}
vector<vector<int>> ans;
for (auto& q : queries) {
int first = q[0], second = q[1];
int val = first ^ second;
if (d.count(val)) {
ans.emplace_back(d[val]);
} else {
ans.push_back({-1, -1});
}
}
return ans;
}
};

• 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]


• func substringXorQueries(s string, queries [][]int) (ans [][]int) {
d := map[int][]int{}
for i := range s {
x := 0
for j := 0; j < 32 && i+j < len(s); j++ {
x = x<<1 | int(s[i+j]-'0')
if _, ok := d[x]; !ok {
d[x] = []int{i, i + j}
}
if x == 0 {
break
}
}
}
for _, q := range queries {
first, second := q[0], q[1]
val := first ^ second
if v, ok := d[val]; ok {
ans = append(ans, v)
} else {
ans = append(ans, []int{-1, -1})
}
}
return
}