Substring XOR Queries solution and explanation
9 more videos on this problem
花花酱 LeetCode 2564. Substring XOR Queries - 刷题找工作 EP410Hua Hua · 11:14 · 2K views
2564. Substring XOR Queries | Weekly Contest 332 | LeetCode 2564Bro Coders · 14:08 · 1K views
Substring XOR Queries - Leetcode 2654 || Weekly Contest - 332Aryan Mittal · 20:15 · 975 views
Substring XOR Queries | leetcode Weekly 332 | Leetcode MediumBinaryMagic · 10:26 · 682 views
2564. Substring XOR Queries | LeetCode MediumDeep Tech · 14:15 · 475 views
Substring XOR Queries | Weekly Contest 332 | LeetcodecodingMohan · 8:54 · 464 views
【每日一题】LeetCode 2564. Substring XOR QueriesHuifeng Guan · 16:17 · 381 views
2564. Substring XOR Queries (Leetcode Medium)Programming Live with Larry · 15:09 · 308 views
2564. Substring XOR Queries | LeetcodeA Code Daily! · 10:39 · 303 views
2564. Substring XOR Queries | LeetCode Weekly 332 | C++Priyanshi Porwal · 10:38 · 164 views
The problem
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
Approach overview
Problem Overview: You are given a binary string s and several queries. Each query contains two integers first and second. Your task is to find the shortest substring of s whose decimal value val satisfies val XOR first = second. If such a substring exists, return its start and end indices; otherwise return [-1, -1]. The key observation is that the required substring value is simply target = first XOR second.
Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)
The straightforward method checks every possible substring of s. Convert each substring from binary to decimal and store its value temporarily. For each query, compute target = first XOR second and search through all generated substrings to find one with that value. This approach repeatedly scans the string and performs binary-to-integer conversions, which leads to O(n²) substrings and expensive repeated work. While simple to implement and useful for understanding the relationship between substring values and XOR, it becomes too slow for large inputs.
Approach 2: Optimized Sliding Window with XOR Properties (O(n * 30) time, O(n) space)
The optimized solution uses the XOR identity val = first XOR second. Instead of processing each query independently, preprocess the binary string and compute the decimal value of substrings starting at every index. Because the maximum query value fits within about 30 bits, only substrings of length up to 30 need to be evaluated. Iterate through s, extend a sliding window up to 30 characters, and build the integer value incrementally using bit operations. Store the first occurrence of each computed value in a hash table mapping value → substring indices.
When answering queries, compute target = first XOR second in constant time. Perform a hash lookup to see if this value was observed during preprocessing. If it exists, return the stored indices; otherwise return [-1, -1]. This approach avoids recomputation and limits substring length using binary constraints. It combines efficient scanning of the string, integer construction via bit manipulation, and constant‑time hash lookups. The preprocessing takes O(n * 30) time and each query is answered in O(1).
Recommended for interviews: Interviewers typically expect the hash‑map preprocessing strategy. The brute force approach demonstrates that you understand substring enumeration and XOR evaluation, but it does not scale. The optimized method shows stronger problem‑solving skills by exploiting XOR algebra and limiting substring length to the number of relevant bits.
Approach 1: Brute Force
This approach involves checking all possible substrings of the given string and calculating their decimal values. For each query, we verify whether there exists a substring whose decimal value XOR with the first value of the query equals the second value. If multiple such substrings exist, we select the one with the smallest starting index.
def substring_xor_queries(s, queries):
def dec_from_binary(sub):
return int(sub, 2)
res = []
length = len(s)
for first, second in queries:
found = False
for start in range(length):
if found:
break
for end in range(start, length):
sub = s[start:end + 1]
val = dec_from_binary(sub)
if val ^ first == second:
res.append([start, end])
found = True
break
if not found:
res.append([-1, -1])
return res
# Test Example
data = {"s": "101101", "queries": [[0, 5], [1, 2]]}
print(substring_xor_queries(data['s'], data['queries']))function substringXorQueries(s, queries) {
function decFromBinary(sub) {
return parseInt(sub, 2);
}
const res = [];
const length = s.length;
for (let [first, second] of queries) {
let found = false;
for (let start = 0; start < length; start++) {
if (found) break;
for (let end = start; end < length; end++) {
const sub = s.slice(start, end + 1);
const val = decFromBinary(sub);
if ((val ^ first) === second) {
res.push([start, end]);
found = true;
break;
}
}
}
if (!found) res.push([-1, -1]);
}
return res;
}
// Test Example
const s = "101101";
const queries = [[0, 5], [1, 2]];
console.log(substringXorQueries(s, queries));The code defines a function to convert a binary substring into a decimal integer, iterates through all possible substrings of the binary string s, and checks the XOR condition for each query. If a valid substring is found, its indices are appended to the results list. Otherwise, [-1, -1] is stored for that query.
Time Complexity: O(n^3) because of the nested loops through the string for each query.
Space Complexity: O(1) for constants aside from the input.
Approach 2: Optimized Sliding Window with XOR Properties
This optimized approach uses the sliding window technique, leveraging the XOR's properties to calculate values dynamically, reducing redundancy of substring recomputation. It aims to minimize both the time complexity compared to brute-force by avoiding recalculations of the entire substring scopes repetitively.
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<List<Integer>> substringXorQueries(String s, int[][] queries) {
List<List<Integer>> result = new ArrayList<>();
int n = s.length();
for (int[] query : queries) {
int first = query[0];
int second = query[1];
boolean found = false;
for (int start = 0; start < n; start++) {
if (found) break;
int num = 0;
for (int end = start; end < n; end++) {
num = (num << 1) | (s.charAt(end) - '0');
if ((num ^ first) == second) {
List<Integer> ans = new ArrayList<>();
ans.add(start);
ans.add(end);
result.add(ans);
found = true;
break;
}
if (num > second + first) break;
}
}
if (!found) {
List<Integer> ans = new ArrayList<>();
ans.add(-1);
ans.add(-1);
result.add(ans);
}
}
return result;
}
// Test Example
public static void main(String[] args) {
Solution solution = new Solution();
String s = "101101";
int[][] queries = { {0, 5}, {1, 2} };
List<List<Integer>> result = solution.substringXorQueries(s, queries);
for (List<Integer> res : result) {
System.out.println(res);
}
}
}using System;
using System.Collections.Generic;
public class Solution {
public IList<IList<int>> SubstringXorQueries(string s, int[][] queries) {
var results = new List<IList<int>>();
int n = s.Length;
foreach (var query in queries) {
int first = query[0];
int second = query[1];
bool found = false;
for (int start = 0; start < n; start++) {
if (found) break;
int number = 0;
for (int end = start; end < n; end++) {
number = (number << 1) + (s[end] - '0');
if ((number ^ first) == second) {
results.Add(new List<int> { start, end });
found = true;
break;
}
if (number > second + first) break;
}
}
if (!found) results.Add(new List<int> { -1, -1 });
}
return results;
}
}
// Test Example
class Program
{
static void Main() {
Solution sol = new Solution();
string s = "101101";
int[][] queries = new int[][] { new int[] { 0, 5 }, new int[] { 1, 2 } };
var result = sol.SubstringXorQueries(s, queries);
foreach(var res in result) {
Console.WriteLine($"[{res[0]}, {res[1]}]");
}
}
}In this Java solution, the logical flow follows similar to the C# code, constructing binary string values dynamically and halting operations to avoid unnecessary calculations.
Time Complexity: O(n^2), similar efficiency intentions with early escape conditions.
Space Complexity: O(n) for managing interim variables and input data.
Approach 3: 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:
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;
}
};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
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force | Time Complexity: O(n^3) because of the nested loops through the string for each query. |
| Optimized Sliding Window with XOR Properties | Time Complexity: O(n^2), similar efficiency intentions with early escape conditions. |
| Preprocessing + Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Enumeration | O(n²) | O(1) | Useful for understanding the problem or when the string size is very small. |
| Sliding Window + Hash Map Precomputation | O(n * 30) + O(q) | O(n) | Best general solution. Efficient when handling many queries on the same binary string. |
Frequently asked questions
Is Substring XOR Queries easy or hard?
Substring XOR Queries is rated Medium difficulty. The challenge comes from recognizing the XOR transformation and limiting substring lengths using bit constraints rather than brute-force enumeration.
Substring XOR Queries Python/Java solution
Most implementations preprocess substring values using a dictionary or HashMap. Python typically uses a dict for value-to-index mapping, while Java uses HashMap<Integer, int[]> to store substring boundaries for constant-time query resolution.
How to solve Substring XOR Queries in O(n)?
Compute the required substring value using target = first XOR second. During preprocessing, iterate through the string and build binary numbers incrementally for substrings up to 30 characters. Store the earliest occurrence of each value in a hash map so queries can be answered with constant-time lookups.
What is the best approach for Substring XOR Queries?
The best approach preprocesses the binary string and stores decimal values of substrings up to length 30 in a hash map. For each query, compute target = first XOR second and look up the value in O(1). This reduces the overall complexity to O(n * 30 + q).
Is Substring XOR Queries asked at Google/Amazon/Meta?
Problems combining XOR logic, hashing, and substring processing frequently appear in interviews at companies like Google, Amazon, and Meta. This problem specifically tests bit manipulation reasoning and efficient preprocessing for multiple queries.
What data structure is used in Substring XOR Queries?
The optimized solution primarily uses a hash map (dictionary) to map computed substring values to their index ranges. Bit manipulation is used to construct integer values efficiently while scanning the binary string.
What is the time complexity of Substring XOR Queries?
The optimized solution runs in O(n * 30 + q) time where n is the length of the binary string and q is the number of queries. Only substrings up to 30 bits are considered because larger values exceed the integer range used in queries.