2564. Substring XOR Queries LeetCode Solution

Last updated: March 5, 2025

In this guide, you will get 2564. Substring XOR Queries LeetCode Solution with the best time and space complexity. The solution to Substring XOR Queries problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Substring XOR Queries solution in C++
Substring XOR Queries solution in Java
Substring XOR Queries solution in Python
Additional Resources

2564. Substring XOR Queries LeetCode Solution image

Problem Statement of Substring XOR Queries

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

Complexity Analysis

Time Complexity: O(30n) = O(n)
Space Complexity: O(n)

2564. Substring XOR Queries LeetCode Solution in C++

class Solution {
 public:
  vector<vector<int>> substringXorQueries(string s,
                                          vector<vector<int>>& queries) {
    constexpr int kMaxBit = 30;
    vector<vector<int>> ans;
    // {val: (left, right)} := s[left..right]'s decimal value = val
    unordered_map<int, pair<int, int>> valToLeftAndRight;

    for (int left = 0; left < s.length(); ++left) {
      int val = 0;
      if (s[left] == '0') {
        // edge case: Save the index of the first 0.
        if (!valToLeftAndRight.contains(0))
          valToLeftAndRight[0] = {left, left};
        continue;
      }
      const int maxRight = min(static_cast<int>(s.length()), left + kMaxBit);
      for (int right = left; right < maxRight; ++right) {
        val = val * 2 + s[right] - '0';
        if (!valToLeftAndRight.contains(val))
          valToLeftAndRight[val] = {left, right};
      }
    }

    for (const vector<int>& query : queries) {
      const int first = query[0];
      const int second = query[1];
      const int val = first ^ second;
      const auto it = valToLeftAndRight.find(val);
      if (it == valToLeftAndRight.cend()) {
        ans.push_back({-1, -1});
      } else {
        const auto [left, right] = it->second;
        ans.push_back({left, right});
      }
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

2564. Substring XOR Queries LeetCode Solution in Java

class Solution {
  public int[][] substringXorQueries(String s, int[][] queries) {
    final int kMaxBit = 30;
    int[][] ans = new int[queries.length][2];
    // {val: (left, right)} := s[left..right]'s decimal value = val
    Map<Integer, Pair<Integer, Integer>> valToLeftAndRight = new HashMap<>();

    for (int left = 0; left < s.length(); ++left) {
      int val = 0;
      if (s.charAt(left) == '0') {
        // edge case: Save the index of the first 0.
        if (!valToLeftAndRight.containsKey(0))
          valToLeftAndRight.put(val, new Pair<>(left, left));
        continue;
      }
      final int maxRight = Math.min(s.length(), left + kMaxBit);
      for (int right = left; right < maxRight; ++right) {
        val = val * 2 + s.charAt(right) - '0';
        if (!valToLeftAndRight.containsKey(val))
          valToLeftAndRight.put(val, new Pair<>(left, right));
      }
    }

    for (int i = 0; i < queries.length; ++i) {
      final int first = queries[i][0];
      final int second = queries[i][1];
      final int val = first ^ second;
      Pair<Integer, Integer> leftAndRight = valToLeftAndRight.get(val);
      if (leftAndRight == null) {
        ans[i] = new int[] {-1, -1};
      } else {
        final int left = leftAndRight.getKey();
        final int right = leftAndRight.getValue();
        ans[i] = new int[] {left, right};
      }
    }

    return ans;
  }
}
// code provided by PROGIEZ

2564. Substring XOR Queries LeetCode Solution in Python

class Solution:
  def substringXorQueries(self, s: str, queries: list[list[int]]) -> list[list[int]]:
    kMaxBit = 30
    # {val: [left, right]} := s[left..right]'s decimal value = val
    valToLeftAndRight = collections.defaultdict(lambda: [-1, -1])

    for left, c in enumerate(s):
      val = 0
      if c == '0':
        # edge case: Save the index of the first 0.
        if 0 not in valToLeftAndRight:
          valToLeftAndRight[0] = [left, left]
        continue
      for right in range(left, min(len(s), left + kMaxBit)):
        val = val * 2 + int(s[right])
        if val not in valToLeftAndRight:
          valToLeftAndRight[val] = [left, right]

    return [valToLeftAndRight[first, right]
            for first, right in queries]
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents