Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2564.html

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 {
        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;
        }
    };
    
  • 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]
    
    
  • 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
    }
    

All Problems

All Solutions