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\).

Python3JavaC++Go

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
}

Comments