Welcome to Subscribe On Youtube
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 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 \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 }