2564. Substring XOR Queries

Medium

302

71

You are given a **binary string** `s`

, and a **2D** integer array `queries`

where `queries[i] = [first`

._{i}, second_{i}]

For the `i`

query, find the ^{th}**shortest substring** of `s`

whose **decimal value**, `val`

, yields `second`

when _{i}**bitwise XORed** with `first`

. In other words, _{i}`val ^ first`

._{i} == second_{i}

The answer to the `i`

query is the endpoints (^{th}**0-indexed**) of the substring `[left`

or _{i}, right_{i}]`[-1, -1]`

if no such substring exists. If there are multiple answers, choose the one with the **minimum** `left`

._{i}

*Return an array* `ans`

*where* `ans[i] = [left`

_{i}, right_{i}]*is the answer to the* `i`

^{th}*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, and`5`

, hence the answer to the first query is`5 ^ 0 = 5`

`[0,2]`

. In the second query, the substring in range`[2,3]`

is"11",and has a decimal value of3, and3. So,`^ 1 = 2`

`[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, and`1`

. So, the answer is`1 ^ 4 = 5`

`[0,0]`

.

**Constraints:**

`1 <= s.length <= 10`

^{4}`s[i]`

is either`'0'`

or`'1'`

.`1 <= queries.length <= 10`

^{5}`0 <= first`

_{i}, second_{i}<= 10^{9}

Accepted

10.1K

Submissions

30K

Acceptance Rate

33.6%

Seen this question in a real interview before?

1/4

Yes

No

Discussion (0)

Related Topics

Copyright ©️ 2023 LeetCode All rights reserved