Skip to content

Latest commit

 

History

History

2564

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 

README.md

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:

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