Substring XOR Queries - Video Solutions

Problem Overview: You are given a binary string s and several queries. Each query contains two integers first and second. Your task is to find the shortest substring of s whose decimal value val satisfies val XOR first = second. If such a substring exists, return its start and end indices; otherwise return [-1, -1]. The key observation is that the required substring value is simply target = first XOR second.

Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)

The straightforward method checks every possible substring of s. Convert each substring from binary to decimal and store its value temporarily. For each query, compute target = first XOR second and search through all generated substrings to find one with that value. This approach repeatedly scans the string and performs binary-to-integer conversions, which leads to O(n²) substrings and expensive repeated work. While simple to implement and useful for understanding the relationship between substring values and XOR, it becomes too slow for large inputs.

Approach 2: Optimized Sliding Window with XOR Properties (O(n * 30) time, O(n) space)

The optimized solution uses the XOR identity val = first XOR second. Instead of processing each query independently, preprocess the binary string and compute the decimal value of substrings starting at every index. Because the maximum query value fits within about 30 bits, only substrings of length up to 30 need to be evaluated. Iterate through s, extend a sliding window up to 30 characters, and build the integer value incrementally using bit operations. Store the first occurrence of each computed value in a hash table mapping value → substring indices.

When answering queries, compute target = first XOR second in constant time. Perform a hash lookup to see if this value was observed during preprocessing. If it exists, return the stored indices; otherwise return [-1, -1]. This approach avoids recomputation and limits substring length using binary constraints. It combines efficient scanning of the string, integer construction via bit manipulation, and constant‑time hash lookups. The preprocessing takes O(n * 30) time and each query is answered in O(1).

Recommended for interviews: Interviewers typically expect the hash‑map preprocessing strategy. The brute force approach demonstrates that you understand substring enumeration and XOR evaluation, but it does not scale. The optimized method shows stronger problem‑solving skills by exploiting XOR algebra and limiting substring length to the number of relevant bits.