What is the primary pattern for solving Substring XOR Queries?

The problem relies on array scanning plus hash lookup to efficiently handle multiple queries and find the shortest valid substring.

How do you efficiently handle large numbers of queries in Substring XOR Queries?

By using a hash map to store previously encountered XOR values and their corresponding indices, you can efficiently resolve queries without redundant calculations.

Why is it important to limit substring length to 30 in Substring XOR Queries?

Limiting the substring length to 30 bits ensures that you only focus on relevant portions of the string, optimizing performance for large inputs.

How can I improve the space complexity of my solution to Substring XOR Queries?

Space complexity can be optimized by using a compact data structure like a hash map to store XOR results, avoiding the need to store unnecessary intermediate data.

What should I do if no valid substring is found in Substring XOR Queries?

Return [-1, -1] when no valid substring matches the required XOR condition, as specified in the problem statement.

#2564

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

子字符串异或查询

给你一个二进制字符串 s 和一个整数数组 queries ，其中 queries[i] = [first i , second i ] 。对于第 i 个查询，找到 s 的最短子字符串，它对应的十进制值 val 与 first i 按位异或得到 second i ，换言之， val ^ …

数组哈希表字符串位运算

题目描述

给你一个 二进制字符串 s 和一个整数数组 queries ，其中 queries[i] = [first_i, second_i] 。

对于第 i 个查询，找到 s 的 最短子字符串 ，它对应的 十进制值 val 与 first_i 按位异或 得到 second_i ，换言之，val ^ first_i == second_i 。

第 i 个查询的答案是子字符串 [left_i, right_i] 的两个端点（下标从 0 开始），如果不存在这样的子字符串，则答案为 [-1, -1] 。如果有多个答案，请你选择 left_i 最小的一个。

请你返回一个数组 ans ，其中 ans[i] = [left_i, right_i] 是第 i 个查询的答案。

子字符串 是一个字符串中一段连续非空的字符序列。

示例 1：

输入：s = "101101", queries = [[0,5],[1,2]]
输出：[[0,2],[2,3]]
解释：第一个查询，端点为 [0,2] 的子字符串为 "101" ，对应十进制数字 5 ，且 5 ^ 0 = 5 ，所以第一个查询的答案为 [0,2]。第二个查询中，端点为 [2,3] 的子字符串为 "11" ，对应十进制数字 3 ，且 3 ^ 1 = 2 。所以第二个查询的答案为 [2,3] 。

示例 2：

输入：s = "0101", queries = [[12,8]]
输出：[[-1,-1]]
解释：这个例子中，没有符合查询的答案，所以返回 [-1,-1] 。

示例 3：

输入：s = "1", queries = [[4,5]]
输出：[[0,0]]
解释：这个例子中，端点为 [0,0] 的子字符串对应的十进制值为 1 ，且 1 ^ 4 = 5 。所以答案为 [0,0] 。

提示：

1 <= s.length <= 10⁴
s[i] 要么是 '0' ，要么是 '1' 。
1 <= queries.length <= 10⁵
0 <= first_i, second_i <= 10⁹

lightbulb

解题思路

方法一：预处理 + 枚举

我们可以先预处理出所有长度为 $1$ 到 $32$ 的子串对应的十进制值，找到每个值对应的最小下标以及对应的右端点下标，存放在哈希表 $d$ 中。

然后枚举每个查询，对于每个查询 $[first, second]$ ，我们只需要在哈希表 $d$ 中查找是否存在键为 $first \oplus second$ 的键值对，如果存在，把对应的最小下标和右端点下标加入答案数组即可，否则加入 $[-1, -1]$ 。

时间复杂度 $O(n \times \log M + m)$ ，空间复杂度 $O(n \times \log M)$ 。其中 $n$ 和 $m$ 分别为字符串 $s$ 和查询数组 $queries$ 的长度，而 $M$ 可以取整数的最大值 $2^{31} - 1$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate should demonstrate a clear understanding of bitwise operations and efficient query handling.
question_mark
An efficient solution will leverage hashing techniques to optimize query resolution, avoiding brute force checks for each substring.
question_mark
Candidates should be able to explain why limiting the substring length to 30 bits is crucial for optimal performance.

warning

常见陷阱

外企场景

error
Failing to limit the substring length to 30 bits, leading to unnecessary computations and performance issues.
error
Overcomplicating the solution by not using a hash map to track XOR values and their indices.
error
Not handling edge cases where no valid substring exists, such as returning [-1, -1] appropriately.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Extend the problem to work with longer binary strings or different types of queries to increase complexity.
arrow_right_alt
Adapt the problem to handle non-binary strings and XOR conditions with different operators.
arrow_right_alt
Consider optimizing for a dynamic set of XOR conditions rather than static queries, introducing more complexity.

help

常见问题

外企场景

继续练习

#2506 统计相似字符串对的数目 #2306 公司命名 #2135 统计追加字母可以获得的单词数