You are given a binary strings, 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 minimumlefti.
Return an arrayanswhereans[i] = [lefti, righti]is the answer to theithquery.
A substring is a contiguous non-empty sequence of characters within a string.
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.
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.
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].
Precompute all possible substrings of s up to length 30 (since 2^30 > 10^9), map their decimal values to their first occurrence. For each query, compute val = firsti ^ secondi and look up the substring.
classSolution {
funsubstringXorQueries(s: String, queries: Array<IntArray>): Array<IntArray> {
val mp = mutableMapOf<Int, Pair<Int, Int>>()
val n = s.length
for (i in0 until n) {
if (s[i] =='0') {
mp.putIfAbsent(0, i to i)
continue }
var valNum = 0for (j in i until minOf(i+30, n)) {
valNum = (valNum shl 1) or (s[j] - '0')
mp.putIfAbsent(valNum, i to j)
}
}
return Array(queries.size) { idx ->val v = queries[idx][0] xor queries[idx][1]
mp[v]?.let { intArrayOf(it.first, it.second) } ?: intArrayOf(-1, -1)
}
}
}
classSolution:
defsubstringXorQueries(self, s: str, queries: list[list[int]]) -> list[list[int]]:
mp = {}
n = len(s)
for i in range(n):
if s[i] =='0':
if0notin mp:
mp[0] = (i, i)
continue val =0for j in range(i, min(i+30, n)):
val = (val <<1) | int(s[j])
if val notin mp:
mp[val] = (i, j)
ans = []
for a, b in queries:
v = a ^ b
if v in mp:
ans.append([mp[v][0], mp[v][1]])
else:
ans.append([-1, -1])
return ans
use std::collections::HashMap;
impl Solution {
pubfnsubstring_xor_queries(s: String, queries: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let n = s.len();
let s = s.as_bytes();
letmut mp = HashMap::new();
for i in0..n {
if s[i] ==b'0' {
mp.entry(0).or_insert((i asi32, i asi32));
continue;
}
letmut val =0;
for j in i..(i+30).min(n) {
val = (val <<1) | (s[j] -b'0') asi32;
mp.entry(val).or_insert((i asi32, j asi32));
}
}
letmut ans = Vec::with_capacity(queries.len());
for q in queries {
let v = q[0] ^ q[1];
iflet Some(&(l, r)) = mp.get(&v) {
ans.push(vec![l, r]);
} else {
ans.push(vec![-1, -1]);
}
}
ans
}
}