#2564

Substring XOR Queries

expert · 1080 · lc medium +32 · premium · verified · 35.5% accepted · 404 likes · top 13%

Description

Given a binary string s and queries where each queries[i] = [firsti, secondi], for each query find the shortest substring of s whose binary integer value val satisfies val ^ firsti == secondi. Return the 0-indexed [left, right] endpoints (the leftmost match among ties), or [-1, -1] if no such substring exists.

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].

Code

1

2

3

class Solution:
    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:

class Solution:
    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]: