Substring XOR Queries - Solution & Explanation
Problem Statement
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.
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.
Code
Python
JavaScript
Complexity
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.
The C# solution uses dynamic calculation of the integer from binary by shifting and adding bits. The solution checks each potential substring for the XOR condition and appends results, using early stopping conditions for efficiency.
Complexity
Time Complexity: O(n^2), given the reduction in redundant calculations.
Space Complexity: O(n) for storing intermediate results and managing the input.
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.
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), given the reduction in redundant calculations. |
| Preprocessing + Enumeration | — |
Detailed 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. |
Video Solution
花花酱 LeetCode 2564. Substring XOR Queries - 刷题找工作 EP410 • Hua Hua • 2,238 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Substring XOR Queries easy or hard?
Substring XOR Queries Python/Java solution
How to solve Substring XOR Queries in O(n)?
What is the best approach for Substring XOR Queries?
Is Substring XOR Queries asked at Google/Amazon/Meta?
What data structure is used in Substring XOR Queries?
What is the time complexity of Substring XOR Queries?
Ready to solve this problem?
Practice Substring XOR Queries with our built-in code editor and test cases.
Practice on FleetCode