Substring XOR Queries

Medium
1339.

Substring XOR Queries

Substring XOR Queries is a medium coding problem on arrays, strings and hash table, asked in Amazon and Google interviews.

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^4
  • s[i] is either '0' or '1'
  • 1 <= queries.length <= 10^5
  • 0 <= firsti, secondi <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number[][]} queries
 * @return {number[][]}
 */
var substringXorQueries = function(s, queries) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^4
  • s[i] is either '0' or '1'
  • 1 <= queries.length <= 10^5
  • 0 <= firsti, secondi <= 10^9

Hints for Substring XOR Queries

  1. Hint 1

    XOR is its own inverse: the condition says val == firsti XOR secondi, a fixed target per query.

  2. 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).

  3. 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

  1. Scan start positions i from left to right. If s[i] is '0', record value 0 at [i, i] if 0 has no entry yet, and move on.
  2. Otherwise extend j from i while j < n and j - i < 30, keeping the running value v = 2v + s[j]; record [i, j] for v if v has no entry yet.
  3. 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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings