# Substring XOR Queries
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/substring-xor-queries)
Canonical: https://scaleengineer.com/dsa/problems/substring-xor-queries
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array, Hash Table, String
**Companies:** [Trilogy](https://scaleengineer.com/companies/trilogy)
---
## 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 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 <= 104`
* `s[i]` is either `'0'` or `'1'`.
* `1 <= queries.length <= 105`
* `0 <= firsti, secondi <= 109`

# Approaches
## Brute-Force per Query
The most straightforward approach is to process each query independently. For every query, we calculate the required decimal value, `val`, by XORing `first` and `second`. Then, we iterate through all possible substrings of the input string `s`, convert each substring from its binary representation to a decimal value, and check if it matches the required `val`. To ensure we find the shortest substring with the minimum left index, we can structure our search by first iterating through substring lengths (from 1 to `s.length()`) and then through their starting positions (from left to right). The first match we find will be the optimal one for that query.
**Time:** O(Q * N * L), where Q is the number of queries, N is the length of `s`, and L is the maximum length of a relevant substring (approx. 31). For each query, we iterate through O(N * L) substrings, and converting each to an integer takes O(L). This results in a total time complexity that is too high for the given constraints. · **Space:** O(1) or O(Q) if we consider the space for the output array, where Q is the number of queries.
**Pros:** Simple to conceptualize and implement.; Requires minimal extra space, only for storing the final answer.
**Cons:** Extremely inefficient and will not pass the time limits for the given constraints.; Repeatedly performs the same substring conversions across different queries.
### Explanation
This brute-force method directly translates the problem statement into a solution. For each of the `Q` queries, we determine the target decimal value. The core of the algorithm is a nested loop structure that generates all substrings of `s`. To meet the problem's criteria for the 'best' substring (shortest, then smallest starting index), we iterate on length `len` from 1 upwards. For a fixed `len`, we iterate on the starting position `i` from 0 upwards. This ensures that the first time we find a substring whose decimal value matches our target, it is guaranteed to be one of the shortest possible length, and among those, the one with the minimum starting index.

```java
class Solution {
    public int[][] substringXorQueries(String s, int[][] queries) {
        int q = queries.length;
        int n = s.length();
        int[][] ans = new int[q][2];

        for (int k = 0; k < q; k++) {
            int first = queries[k][0];
            int second = queries[k][1];
            int target = first ^ second;
            
            int[] currentAns = {-1, -1};
            int minLength = Integer.MAX_VALUE;

            // Iterate through all substrings
            for (int i = 0; i < n; i++) {
                long currentVal = 0;
                for (int j = i; j < n; j++) {
                    // Optimization: limit substring length to avoid overflow and unnecessary work
                    if (j - i + 1 > 32) break;
                    
                    currentVal = (currentVal << 1) | (s.charAt(j) - '0');
                    
                    if (currentVal == target) {
                        int currentLength = j - i + 1;
                        if (currentLength < minLength) {
                            minLength = currentLength;
                            currentAns[0] = i;
                            currentAns[1] = j;
                        } 
                        // The problem asks for min left for the same length.
                        // A better loop structure is needed to avoid this check.
                        // Iterating by length first is better.
                    }
                }
            }
            ans[k] = currentAns;
        }
        // The above code finds shortest, but not necessarily min-left first.
        // A correct brute-force would be:
        for (int k = 0; k < q; k++) {
            int target = queries[k][0] ^ queries[k][1];
            ans[k] = new int[]{-1, -1};
            boolean found = false;
            for (int len = 1; len <= n; len++) {
                if (len > 32) break; // Optimization
                for (int i = 0; i <= n - len; i++) {
                    int j = i + len - 1;
                    String sub = s.substring(i, j + 1);
                    try {
                        int val = Integer.parseInt(sub, 2);
                        if (val == target) {
                            ans[k][0] = i;
                            ans[k][1] = j;
                            found = true;
                            break;
                        }
                    } catch (NumberFormatException e) { /* Value too large */ }
                }
                if (found) break;
            }
        }
        return ans;
    }
}
```
### Algorithm
- For each query `[first, second]`:
  1. Calculate the target value: `target = first ^ second`.
  2. Initialize a flag `found = false` and a result array `ans_i = [-1, -1]`.
  3. Iterate through possible substring lengths `len` from 1 to the length of `s`.
  4. For each `len`, iterate through all possible starting indices `i` from 0 to `s.length() - len`.
  5. Extract the substring `sub = s.substring(i, i + len)`.
  6. Convert `sub` to its decimal value `val`. Be mindful of potential `NumberFormatException` for long substrings, although we only need to consider lengths up to about 31.
  7. If `val` equals `target`, we have found the shortest substring with the minimum left index due to the loop order. Set `ans_i = [i, i + len - 1]`, set `found = true`, and break from all loops for the current query.
  8. If `found` is true, stop searching for the current query.
- After checking all possibilities for a query, if no match was found, the answer remains `[-1, -1]`.
- Collect the answers for all queries and return them.

## Precomputation with Hash Map
Observing that the string `s` is the same for all queries, we can pre-process `s` to answer each query much faster. The idea is to find all possible decimal values that can be formed by substrings of `s` and store the location of their first optimal occurrence in a hash map. The map will have the decimal value as the key and the `[left, right]` indices as the value. By iterating through substring lengths and then their positions, we ensure that the first time we encounter a decimal value, it corresponds to its shortest representation with the minimum left index. After this precomputation, each query can be answered in constant time on average with a simple map lookup.
**Time:** O(N * L^2 + Q). The precomputation involves a loop over lengths `L`, a loop over `N` positions, and a substring conversion taking `O(L)`. This gives `O(N * L^2)`. The query processing part takes O(Q) for `Q` queries. · **Space:** O(N * L), where N is the length of `s` and L is the max substring length (31). The hash map can store up to this many unique values in the worst case.
**Pros:** Drastically reduces query time to O(1) on average.; Overall time complexity is dominated by the one-time precomputation, making it very efficient for a large number of queries.
**Cons:** Requires significant auxiliary space for the hash map, potentially up to O(N * L) entries.; The precomputation step involves redundant work, as substring-to-integer conversions are not optimized.
### Explanation
This approach separates the problem into two phases: precomputation and query processing. 

In the precomputation phase, we build a map that stores the best possible `[left, right]` pair for every decimal value representable by a substring of `s`. The maximum value of `first_i ^ second_i` is less than `2^31`, so we only need to consider substrings of length up to 31. We iterate through lengths `len` from 1 to 31, and for each length, we iterate through all possible start indices `i`. This order guarantees that we process shorter substrings before longer ones, and for a given length, we process substrings with smaller start indices first. When we calculate a decimal value `val` from a substring, we check if it's already in our map. If not, we add it, mapping it to the current `[i, i + len - 1]`. If it's already present, we do nothing, because the existing entry must be better or equal according to the problem's criteria.

In the query processing phase, for each query, we calculate the `target` value and perform a quick lookup in our precomputed map. This is highly efficient.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[][] substringXorQueries(String s, int[][] queries) {
        int n = s.length();
        Map<Integer, int[]> valToPos = new HashMap<>();

        // Precomputation
        for (int len = 1; len <= 31 && len <= n; ++len) {
            for (int i = 0; i <= n - len; ++i) {
                int j = i + len - 1;
                try {
                    int val = Integer.parseInt(s.substring(i, j + 1), 2);
                    if (!valToPos.containsKey(val)) {
                        valToPos.put(val, new int[]{i, j});
                    }
                } catch (NumberFormatException e) {
                    // This can happen if the binary string represents a number > Integer.MAX_VALUE
                    // but our length limit of 31 prevents this for positive numbers.
                }
            }
        }

        // Query Processing
        int q = queries.length;
        int[][] ans = new int[q][2];
        int[] notFound = {-1, -1};
        for (int i = 0; i < q; ++i) {
            int target = queries[i][0] ^ queries[i][1];
            ans[i] = valToPos.getOrDefault(target, notFound);
        }

        return ans;
    }
}
```
### Algorithm
- Initialize a `HashMap<Integer, int[]>` named `valToPos` to store the mapping from a decimal value to its optimal `[left, right]` indices.
- Precomputation Phase:
  1. Iterate through substring lengths `len` from 1 to 31 (as values larger than `2^31-1` are not needed).
  2. For each `len`, iterate through starting positions `i` from 0 to `s.length() - len`.
  3. Extract the substring `s.substring(i, i + len - 1)`.
  4. Convert this substring to its integer value `val`.
  5. If `valToPos` does not contain `val` as a key, add it: `valToPos.put(val, new int[]{i, i + len - 1})`.
- Query Processing Phase:
  1. For each query `[first, second]`, calculate `target = first ^ second`.
  2. Look up `target` in `valToPos`. 
  3. If `target` is found, the answer is `valToPos.get(target)`.
  4. Otherwise, the answer is `[-1, -1]`.

## Optimized Precomputation
This approach refines the precomputation strategy to achieve better time complexity. Instead of iterating by length and position, we iterate through each possible starting position `i` in `s`. For each `i`, we generate all substrings starting at `i` (up to length 31) and calculate their values incrementally. A key insight is that any positive integer's shortest binary representation must start with '1'. This allows us to largely ignore substrings that begin with '0' (except for the value 0 itself, represented by "0"). By processing start indices `i` from left to right, we ensure that the first time we encounter a value, it's from its first possible occurrence, automatically satisfying the 'minimum left index' requirement. This eliminates the nested loop over lengths and the repeated `parseInt` calls, leading to a more efficient `O(N*L)` precomputation.
**Time:** O(N * L + Q). The precomputation takes O(N * L) because for each of the N starting positions, we iterate at most L steps. Query processing takes O(Q). This is the optimal time complexity. · **Space:** O(N * L), where N is `s.length()` and L is the max substring length (31). The space is for the hash map.
**Pros:** The most time-efficient solution with O(N * L + Q) complexity.; Answers queries in O(1) average time after precomputation.; Optimizes precomputation by avoiding redundant calculations for non-canonical binary strings.
**Cons:** Still requires O(N * L) space for the hash map, which can be considerable for large N.; The logic is slightly more nuanced due to the optimization based on canonical binary representations.
### Explanation
This optimized method improves the precomputation step of the previous approach. We iterate through the string `s` with a single main loop for the starting position `i`. 

For each `i`, we build up numbers by extending a substring to the right. If `s[i]` is '1', we start a nested loop for the end position `j`. The decimal value is calculated efficiently using bitwise shifts (`val = (val << 1) | ...`). Since we iterate `i` from 0 to `n-1`, the first time we encounter any value, it will be at its leftmost occurrence. Because we only consider substrings starting with '1' for positive numbers, we are guaranteed to be processing their shortest (canonical) binary representation. The special case of value 0 is handled by finding the first '0' in the string. This avoids the `O(L^2)` factor in the precomputation, bringing it down to `O(N*L)`.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[][] substringXorQueries(String s, int[][] queries) {
        int n = s.length();
        Map<Integer, int[]> valToPos = new HashMap<>();
        int[] notFound = {-1, -1};

        // Precomputation
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) == '0') {
                if (!valToPos.containsKey(0)) {
                    valToPos.put(0, new int[]{i, i});
                }
                continue;
            }
            
            long val = 0;
            for (int j = i; j < n; ++j) {
                val = (val << 1) | (s.charAt(j) - '0');
                // Max possible target is around 2*10^9, which is < 2^31.
                // A long with value > 2^31 is safe to break.
                if (val > 2_000_000_000L + 7) { // A safe upper bound
                    break;
                }
                if (!valToPos.containsKey((int)val)) {
                    valToPos.put((int)val, new int[]{i, j});
                }
            }
        }

        // Query Processing
        int q = queries.length;
        int[][] ans = new int[q][2];
        for (int i = 0; i < q; ++i) {
            int target = queries[i][0] ^ queries[i][1];
            ans[i] = valToPos.getOrDefault(target, notFound);
        }

        return ans;
    }
}
```
### Algorithm
- Initialize a `HashMap<Integer, int[]>` named `valToPos`.
- Precomputation Phase:
  1. Iterate through each starting index `i` from 0 to `s.length() - 1`.
  2. If `s.charAt(i)` is '0', this corresponds to the value 0. If 0 is not yet in `valToPos`, add `valToPos.put(0, new int[]{i, i})`. Then, continue to the next `i`, as any other substring starting with '0' (e.g., "01") is not a canonical shortest representation.
  3. If `s.charAt(i)` is '1', start building a number.
  4. Initialize `long val = 0`.
  5. Iterate `j` from `i` up to `min(s.length() - 1, i + 30)`.
  6. Update the value incrementally: `val = (val << 1) | (s.charAt(j) - '0')`.
  7. If `val` exceeds the maximum possible query value, break the inner loop.
  8. If `valToPos` does not contain `(int)val`, add `valToPos.put((int)val, new int[]{i, j})`.
- Query Processing Phase:
  1. For each query `[first, second]`, calculate `target = first ^ second`.
  2. Look up `target` in `valToPos`.
  3. If found, use the stored `[left, right]`. Otherwise, use `[-1, -1]`.

# Solutions
### Java

```java
class Solution {
public
  int[][] substringXorQueries(String s, int[][] queries) {
    Map<Integer, int[]> d = new HashMap<>();
    int n = s.length();
    for (int i = 0; i < n; ++i) {
      int x = 0;
      for (int j = 0; j < 32 && i + j < n; ++j) {
        x = x << 1 | (s.charAt(i + j) - '0');
        d.putIfAbsent(x, new int[]{i, i + j});
        if (x == 0) {
          break;
        }
      }
    }
    int m = queries.length;
    int[][] ans = new int[m][2];
    for (int i = 0; i < m; ++i) {
      int first = queries[i][0], second = queries[i][1];
      int val = first ^ second;
      ans[i] = d.getOrDefault(val, new int[]{-1, -1});
    }
    return ans;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
class Solution:
    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]: d = {} n = len(s) for i in range(n): x = 0 for j in range(32): if i + j >= n: break x = x << 1 | int(s[i + j]) if x not in d: d[x] = [i, i + j] if x == 0: break return [d . get(first ^ second, [- 1, - 1]) for first, second in queries]

```