Question

2564. Substring XOR Queries

中文文档

Description

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

Solutions

Solution 1: Preprocessing + Enumeration

We can first preprocess all substrings of length $1$ to $32$ into their corresponding decimal values, find the minimum index and the corresponding right endpoint index for each value, and store them in the hash table $d$.

Then we enumerate each query. For each query $[first, second]$, we only need to check in the hash table $d$ whether there exists a key-value pair with the key as $first \oplus second$. If it exists, add the corresponding minimum index and right endpoint index to the answer array. Otherwise, add $[-1, -1]$.

The time complexity is $O(n \times \log M + m)$, and the space complexity is $O(n \times \log M)$. Where $n$ and $m$ are the lengths of the string $s$ and the query array $queries$ respectively, and $M$ can take the maximum value of an integer $2^{31} - 1$.

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]

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

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

func substringXorQueries(s string, queries [][]int) (ans [][]int) {
  d := map[int][]int{}
  for i := range s {
    x := 0
    for j := 0; j < 32 && i+j < len(s); j++ {
      x = x<<1 | int(s[i+j]-'0')
      if _, ok := d[x]; !ok {
        d[x] = []int{i, i + j}
      }
      if x == 0 {
        break
      }
    }
  }
  for _, q := range queries {
    first, second := q[0], q[1]
    val := first ^ second
    if v, ok := d[val]; ok {
      ans = append(ans, v)
    } else {
      ans = append(ans, []int{-1, -1})
    }
  }
  return
}