2564

2564. Substring XOR Queries (Medium)

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

Companies: Trilogy

Related Topics:
Array, Hash Table, String, Bit Manipulation

Similar Questions:

• String Matching in an Array (Easy)

Hints:

• You do not need to consider substrings having lengths greater than 30.
• Pre-process all substrings with lengths not greater than 30, and add the best endpoints to a dictionary.

Solution 1.

// OJ: https://leetcode.com/problems/substring-xor-queries
// Author: github.com/lzl124631x
// Time: O(N + Q)
// Space: O(Q) extra space
class Solution {
public:
    vector<vector<int>> substringXorQueries(string s, vector<vector<int>>& Q) {
        vector<vector<int>> ans(Q.size(), {-1,-1});
        unordered_map<int, vector<int>> m;
        for (int i = 0; i < Q.size(); ++i) m[Q[i][0] ^ Q[i][1]].push_back(i); 
        for (int i = 0, b = 0; i < s.size(); ++i) {
            b = (b << 1) + s[i] - '0';
            for (int j = 1; j < 32; ++j) {
                int v = (((unsigned)1 << j) - 1) & b;
                if (m.count(v) == 0) continue;
                for (int idx : m[v]) ans[idx] = {i - j + 1, i};
                m.erase(v);
            }
        }
        return ans;
    }
};