Substring XOR Queries - Practice Coding Problems

Substring XOR Queries - Problem

You are given a binary string s, and a 2D integer array queries where queries[i] = [first_i, second_i].

For the i^th query, find the shortest substring of s whose decimal value, val, yields second_i when bitwise XORed with first_i. In other words, val ^ first_i == second_i.

The answer to the i^th query is the endpoints (0-indexed) of the substring [left_i, right_i] or [-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.

Input & Output

Example 1 — Basic Case

$ Input: s = "101101", queries = [[4,7],[2,3]]

› Output: [[2,3],[1,2]]

💡 Note: For query [4,7]: target = 4^7 = 3. Substring "11" at indices [2,3] has decimal value 3. For query [2,3]: target = 2^3 = 1. Substring "01" at indices [1,2] has decimal value 1.

Example 2 — No Solution

$ Input: s = "0101", queries = [[5,1]]

› Output: [[-1,-1]]

💡 Note: Target = 5^1 = 4. No substring of "0101" has decimal value 4, so return [-1,-1].

Example 3 — Single Character

$ Input: s = "1", queries = [[3,2]]

› Output: [[0,0]]

💡 Note: Target = 3^2 = 1. Substring "1" at indices [0,0] has decimal value 1.

Constraints

1 ≤ s.length ≤ 10⁴
s[i] is either '0' or '1'
1 ≤ queries.length ≤ 10⁵
0 ≤ first_i, second_i ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Binary string and query pairs [first, second]

Process

Find substring where decimal_value ^ first == second

Output

Return [start, end] indices of shortest leftmost match

Key Takeaway

🎯 Key Insight: XOR relationship means target = first ^ second, then find substring with that decimal value

Asked in

M Microsoft 15 G Google 12 A Amazon 8

The key insight is to understand that for each query, we need to find a substring whose decimal value XOR with the first parameter equals the second parameter. The target value is first ^ second. The best approach depends on constraints: pre-computing all substring values gives O(1) query time but uses O(n²) space, while optimized brute force with early termination provides good practical performance. Time: O(n² + q) with preprocessing or O(n×q) optimized, Space: O(n²) or O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³ × q)	O(1)	For each query, check all possible substrings to find the shortest match
Pre-compute All Substrings	O(n² + q)	O(n²)	Pre-compute all substring values and store their positions in a hash map
Optimized with Early Termination	O(n × min(n, 30) × q)	O(1)	Enhanced brute force with pruning and limited substring length

Brute Force — Algorithm Steps

For each query, iterate through all possible substring start positions
For each start position, extend to all possible end positions
Convert binary substring to decimal and check XOR condition

Visualization

Tap to expand

Step-by-Step Walkthrough

Input

Binary string and query values

Generate

Create all possible substrings

Check

Test XOR condition for each substring

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

void solution(char* s, int queries[][2], int queryCount, int result[][2]) {
    int n = strlen(s);
    
    for (int q = 0; q < queryCount; q++) {
        int first = queries[q][0];
        int second = queries[q][1];
        int target = first ^ second;
        result[q][0] = -1;
        result[q][1] = -1;
        int minLen = INT_MAX;
        
        for (int i = 0; i < n; i++) {
            long long val = 0;
            for (int j = i; j < n; j++) {
                val = val * 2 + (s[j] - '0');
                if (val == target) {
                    if (j - i + 1 < minLen) {
                        minLen = j - i + 1;
                        result[q][0] = i;
                        result[q][1] = j;
                        break;
                    }
                } else if (val > target) {
                    break;
                }
            }
        }
    }
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char line[1000000];
    fgets(line, sizeof(line), stdin);
    
    int queries[1000][2];
    int queryCount = 0;
    
    char* ptr = line + 1;
    while (*ptr != ']' && *ptr != '\0') {
        if (*ptr == '[') {
            sscanf(ptr, "[%d,%d]", &queries[queryCount][0], &queries[queryCount][1]);
            queryCount++;
        }
        ptr++;
    }
    
    int result[1000][2];
    solution(s, queries, queryCount, result);
    
    printf("[");
    for (int i = 0; i < queryCount; i++) {
        printf("[%d,%d]", result[i][0], result[i][1]);
        if (i < queryCount - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³ × q)

For q queries, each checks O(n²) substrings with O(n) conversion time

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables for computation, no extra data structures

✓ Linear Space

8.5K Views

Medium Frequency

~25 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler