Substring XOR Queries — Solution in Python, Java & C++
Substring XOR Queries solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Substring XOR Queries is a medium coding problem on arrays, strings and hash table, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Hash Table, Bit Manipulation
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a binary string s and an array queries with queries[i] = [firsti, secondi].
For query i, find the shortest substring of s whose decimal value val (reading the substring as a binary number, leading zeros allowed) satisfies val XOR firsti == secondi. The answer is the pair [lefti, righti] of the substring's 0-indexed endpoints (inclusive). If several shortest substrings qualify, take the one with the smallest lefti; if none exists, the answer is [-1, -1].
Return the array of answers.
Example 1
Input: s = "1101", queries = [[2,1],[0,0],[7,1]]
Output: [[0,1],[2,2],[0,2]]
Explanation: The targets are `2 XOR 1 = 3` ("11"), 0 ("0") and `7 XOR 1 = 6` ("110").
Example 2
Input: s = "0101", queries = [[12,2]]
Output: [[-1,-1]]
Explanation: The target 14 is "1110", which does not occur.
Example 3
Input: s = "1", queries = [[4,5]]
Output: [[0,0]]
Constraints
1 <= s.length <= 10^4s[i] is either '0' or '1'1 <= queries.length <= 10^50 <= firsti, secondi <= 10^9
Hints for Substring XOR Queries
Hint 1
XOR is its own inverse: the condition says
val == firsti XOR secondi, a fixed target per query.Hint 2
Targets are below 2^30, and a shortest substring with a positive value cannot start with a 0 — so only substrings that start with '1' and have at most 30 characters matter (plus a single '0' for target 0).
Hint 3
Precompute, for every such substring value, its first occurrence (scanning start positions left to right), then answer each query with one lookup.
How to solve Substring XOR Queries
Each query just asks for the target firsti XOR secondi. Every useful substring is short — at most 30 characters, starting with '1' unless the target is 0 — so all of them can be tabulated in advance.
Approach
- Scan start positions
ifrom left to right. Ifs[i]is '0', record value 0 at[i, i]if 0 has no entry yet, and move on. - Otherwise extend
jfromiwhilej < nandj - i < 30, keeping the running valuev = 2v + s[j]; record[i, j]forvifvhas no entry yet. - For each query, look up
firsti XOR secondi; return its entry or[-1, -1].
Why it works
For a positive target, any substring with leading zeros has a shorter suffix with the same value, so the shortest ones start with '1' and all have exactly the target's bit length. Among those, recording only the first time a value is seen while scanning starts left to right yields the smallest left end. The target 0 is best served by the leftmost single '0'. Targets never exceed 2^30 - 1, so 30 characters suffice.
Complexity
- Time —
O(30 · n + q) - Space —
O(30 · n)
Pitfalls
- Do not record substrings that start with '0' (except the single '0'): with leading zeros they are not the shortest.
- Stop extending after 30 characters — longer values exceed every possible target and overflow 32-bit integers.
- Ties go to the smallest left index, which the left-to-right scan with "record only if absent" gives for free.
Reference solution
Python
from typing import List
def substringXorQueries(s: str, queries: List[List[int]]) -> List[List[int]]:
n = len(s)
seen = {}
for i in range(n):
if s[i] == "0":
if 0 not in seen:
seen[0] = [i, i]
continue
v = 0
for j in range(i, min(n, i + 30)):
v = v * 2 + (1 if s[j] == "1" else 0)
if v not in seen:
seen[v] = [i, j]
return [seen.get(a ^ b, [-1, -1]) for a, b in queries]Java
public static int[][] substringXorQueries(String s, int[][] queries) {
int n = s.length();
HashMap<Integer, int[]> seen = new HashMap<>();
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '0') {
if (!seen.containsKey(0)) seen.put(0, new int[] {i, i});
continue;
}
int v = 0;
for (int j = i; j < n && j < i + 30; j++) {
v = v * 2 + (s.charAt(j) - '0');
if (!seen.containsKey(v)) seen.put(v, new int[] {i, j});
}
}
int[][] ans = new int[queries.length][];
for (int q = 0; q < queries.length; q++) {
int[] hit = seen.get(queries[q][0] ^ queries[q][1]);
ans[q] = hit == null ? new int[] {-1, -1} : new int[] {hit[0], hit[1]};
}
return ans;
}C++
vector<vector<int>> substringXorQueries(string s, vector<vector<int>>& queries) {
int n = s.size();
unordered_map<int, pair<int, int>> seen;
for (int i = 0; i < n; i++) {
if (s[i] == '0') {
if (!seen.count(0)) seen[0] = make_pair(i, i);
continue;
}
int v = 0;
for (int j = i; j < n && j < i + 30; j++) {
v = v * 2 + (s[j] - '0');
if (!seen.count(v)) seen[v] = make_pair(i, j);
}
}
vector<vector<int>> ans;
for (auto& q : queries) {
auto it = seen.find(q[0] ^ q[1]);
if (it == seen.end()) ans.push_back({-1, -1});
else ans.push_back({it->second.first, it->second.second});
}
return ans;
}JavaScript
var substringXorQueries = function(s, queries) {
var n = s.length, seen = new Map();
for (var i = 0; i < n; i++) {
if (s[i] === "0") {
if (!seen.has(0)) seen.set(0, [i, i]);
continue;
}
var v = 0;
for (var j = i; j < n && j < i + 30; j++) {
v = v * 2 + (s[j] === "1" ? 1 : 0);
if (!seen.has(v)) seen.set(v, [i, j]);
}
}
return queries.map(function(q) {
var hit = seen.get(q[0] ^ q[1]);
return hit ? hit.slice() : [-1, -1];
});
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.