2564. Substring XOR Queries

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.

class Solution {

public:
    vector<vector<int>> substringXorQueries(string s, vector<vector<int>>& queries) {
        unordered_map<int, vector<int>> mp;
        for(int i = 0; i < queries.size(); i++) {
            auto bit = queries[i][0] ^ queries[i][1];
            mp[bit].push_back(i);
        }
        vector<vector<int>> res(queries.size(), {-1,-1});
        for(int len = 1; len <= 30; len++) {
            long long mask = (1ll<<len) - 1;
            for(long long i = 0, now = 0; i < s.length(); i++) {
                now = (now * 2 + s[i] - '0') & mask;
                if(i + 1 >= len) {
                    if(mp.count(now)) {
                        for(auto idx : mp[now]) {
                            res[idx] = {(int)i-len+1,(int)i};
                        }
                        mp.erase(now);
                    }
                }
            }
        }
        return res;
    }
};