Substring XOR Queries

Welcome to the world of Substring XOR Queries! If you thought finding a needle in a haystack was tough, try finding a substring that matches a specific XOR value in a binary string. It’s like trying to find your car keys in a dark room—good luck with that!

Problem Description

Imagine you have a binary string, and you want to answer a series of queries. Each query consists of two integers, and your task is to find a substring in the binary string such that the XOR of the substring’s decimal value equals the XOR of the two integers in the query. Sounds simple, right? Well, it’s not! It’s like trying to convince your cat to take a bath—nearly impossible!

For example, if your binary string is “1101” and your query is (1, 2), you need to find a substring whose decimal value equals 3 (because 1 XOR 2 = 3).

Code Solution


class Solution {
  public int[][] substringXorQueries(String s, int[][] queries) {
    final int kMaxBit = 30;
    int[][] ans = new int[queries.length][2];
    Map> valToLeftAndRight = new HashMap<>();

    for (int left = 0; left < s.length(); ++left) {
      int val = 0;
      if (s.charAt(left) == '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 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;
  }
}

Approach Explanation

The code works by first creating a mapping of all possible decimal values of substrings in the binary string to their respective indices. It then processes each query by calculating the XOR of the two integers and checking if that value exists in the mapping. If it does, it retrieves the indices; if not, it returns [-1, -1].

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n * k), where n is the length of the string and k is the maximum number of bits (30 in this case).
Space Complexity	O(n), as we are storing the indices of the substrings in a map.

Real-World Example

Think of it like trying to find the perfect recipe for a dish using a limited set of ingredients. You have a list of ingredients (the binary string) and a couple of recipes (the queries). Each recipe requires a specific combination of ingredients (the XOR value). Your job is to find out if you can whip up that dish with what you have. If you can, great! If not, well, it’s back to the drawing board.

Navigation Links

If you want to check out the solutions in other languages, click below: