Substring XOR Queries

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.

Examples

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 of **5** , and **5 ^ 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 of **1** , and **1 ^ 4 = 5**. So, the answer is [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

Solution

Method 1 – Hash Map of All Substrings

Intuition

Precompute all possible substrings of s up to length 30 (since 2^30 > 10^9), map their decimal values to their first occurrence. For each query, compute val = firsti ^ secondi and look up the substring.

Approach

1. For each index in s, for substring lengths up to 30, compute the decimal value and store the first occurrence in a hash map.
2. For each query, compute val = firsti ^ secondi and look up in the map.
3. If found, return the corresponding indices; else, return [-1, -1].

Code

C++

class Solution {
public:
    vector<vector<int>> substringXorQueries(string s, vector<vector<int>>& queries) {
        unordered_map<int, pair<int,int>> mp;
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            if (s[i] == '0') {
                if (!mp.count(0)) mp[0] = {i, i};
                continue;
            }
            int val = 0;
            for (int j = i; j < min(i+30, n); ++j) {
                val = (val << 1) | (s[j] - '0');
                if (!mp.count(val)) mp[val] = {i, j};
            }
        }
        vector<vector<int>> ans;
        for (auto& q : queries) {
            int v = q[0] ^ q[1];
            if (mp.count(v)) ans.push_back({mp[v].first, mp[v].second});
            else ans.push_back({-1, -1});
        }
        return ans;
    }
};

Go

func substringXorQueries(s string, queries [][]int) [][]int {
    mp := map[int][2]int{}
    n := len(s)
    for i := 0; i < n; i++ {
        if s[i] == '0' {
            if _, ok := mp[0]; !ok {
                mp[0] = [2]int{i, i}
            }
            continue
        }
        val := 0
        for j := i; j < i+30 && j < n; j++ {
            val = (val << 1) | int(s[j]-'0')
            if _, ok := mp[val]; !ok {
                mp[val] = [2]int{i, j}
            }
        }
    }
    ans := make([][]int, len(queries))
    for idx, q := range queries {
        v := q[0] ^ q[1]
        if p, ok := mp[v]; ok {
            ans[idx] = []int{p[0], p[1]}
        } else {
            ans[idx] = []int{-1, -1}
        }
    }
    return ans
}

Java

import java.util.*;
class Solution {
    public int[][] substringXorQueries(String s, int[][] queries) {
        Map<Integer, int[]> mp = new HashMap<>();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '0') {
                mp.putIfAbsent(0, new int[]{i, i});
                continue;
            }
            int val = 0;
            for (int j = i; j < Math.min(i+30, n); j++) {
                val = (val << 1) | (s.charAt(j) - '0');
                mp.putIfAbsent(val, new int[]{i, j});
            }
        }
        int[][] ans = new int[queries.length][2];
        for (int idx = 0; idx < queries.length; idx++) {
            int v = queries[idx][0] ^ queries[idx][1];
            if (mp.containsKey(v)) ans[idx] = mp.get(v);
            else ans[idx] = new int[]{-1, -1};
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun substringXorQueries(s: String, queries: Array<IntArray>): Array<IntArray> {
        val mp = mutableMapOf<Int, Pair<Int, Int>>()
        val n = s.length
        for (i in 0 until n) {
            if (s[i] == '0') {
                mp.putIfAbsent(0, i to i)
                continue
            }
            var valNum = 0
            for (j in i until minOf(i+30, n)) {
                valNum = (valNum shl 1) or (s[j] - '0')
                mp.putIfAbsent(valNum, i to j)
            }
        }
        return Array(queries.size) { idx ->
            val v = queries[idx][0] xor queries[idx][1]
            mp[v]?.let { intArrayOf(it.first, it.second) } ?: intArrayOf(-1, -1)
        }
    }
}

Python

class Solution:
    def substringXorQueries(self, s: str, queries: list[list[int]]) -> list[list[int]]:
        mp = {}
        n = len(s)
        for i in range(n):
            if s[i] == '0':
                if 0 not in mp:
                    mp[0] = (i, i)
                continue
            val = 0
            for j in range(i, min(i+30, n)):
                val = (val << 1) | int(s[j])
                if val not in mp:
                    mp[val] = (i, j)
        ans = []
        for a, b in queries:
            v = a ^ b
            if v in mp:
                ans.append([mp[v][0], mp[v][1]])
            else:
                ans.append([-1, -1])
        return ans

Rust

use std::collections::HashMap;
impl Solution {
    pub fn substring_xor_queries(s: String, queries: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let n = s.len();
        let s = s.as_bytes();
        let mut mp = HashMap::new();
        for i in 0..n {
            if s[i] == b'0' {
                mp.entry(0).or_insert((i as i32, i as i32));
                continue;
            }
            let mut val = 0;
            for j in i..(i+30).min(n) {
                val = (val << 1) | (s[j] - b'0') as i32;
                mp.entry(val).or_insert((i as i32, j as i32));
            }
        }
        let mut ans = Vec::with_capacity(queries.len());
        for q in queries {
            let v = q[0] ^ q[1];
            if let Some(&(l, r)) = mp.get(&v) {
                ans.push(vec![l, r]);
            } else {
                ans.push(vec![-1, -1]);
            }
        }
        ans
    }
}

TypeScript

class Solution {
    substringXorQueries(s: string, queries: number[][]): number[][] {
        const n = s.length;
        const mp = new Map<number, [number, number]>();
        for (let i = 0; i < n; i++) {
            if (s[i] === '0') {
                if (!mp.has(0)) mp.set(0, [i, i]);
                continue;
            }
            let val = 0;
            for (let j = i; j < Math.min(i+30, n); j++) {
                val = (val << 1) | (s[j] === '1' ? 1 : 0);
                if (!mp.has(val)) mp.set(val, [i, j]);
            }
        }
        return queries.map(([a, b]) => {
            const v = a ^ b;
            return mp.has(v) ? [...mp.get(v)!] : [-1, -1];
        });
    }
}

Complexity

• ⏰ Time complexity: O(n * 30 + q) — Each substring up to length 30 is processed, and each query is answered in O(1).
• 🧺 Space complexity: O(n * 30) — For storing all possible substrings up to length 30.