Scale Engineer

Substring XOR Queries

Med
#2344Time: O(Q * N * L), where Q is the number of queries, N is the length of `s`, and L is the maximum length of a relevant substring (approx. 31). For each query, we iterate through O(N * L) substrings, and converting each to an integer takes O(L). This results in a total time complexity that is too high for the given constraints.Space: O(1) or O(Q) if we consider the space for the output array, where Q is the number of queries.1 company
Patterns
Bit Manipulation
Data structures
ArrayHash TableString
Companies
Trilogy

Prompt

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

For the ith query, find the shortest substring of s whose decimal value, val, yields secondi when bitwise XORed with firsti. In other words, val ^ firsti == secondi.

The answer to the ith query is the endpoints (0-indexed) of the substring [lefti, righti] or [-1, -1] if no such substring exists. If there are multiple answers, choose the one with the minimum lefti.

Return an array ans where ans[i] = [lefti, righti] is the answer to the ith query.

A substring is a contiguous non-empty sequence of characters within a string.

 

Example 1:

[0,2]

Example 2:

[-1,-1] is returned

Example 3:

[0,0]

 

Constraints:

  • 1 <= s.length <= 104
  • s[i] is either '0' or '1'.
  • 1 <= queries.length <= 105
  • 0 <= firsti, secondi <= 109

Approaches

3 approaches with complexity analysis and trade-offs.

The most straightforward approach is to process each query independently. For every query, we calculate the required decimal value, val, by XORing first and second. Then, we iterate through all possible substrings of the input string s, convert each substring from its binary representation to a decimal value, and check if it matches the required val. To ensure we find the shortest substring with the minimum left index, we can structure our search by first iterating through substring lengths (from 1 to s.length()) and then through their starting positions (from left to right). The first match we find will be the optimal one for that query.

Algorithm

  • For each query [first, second]:
    1. Calculate the target value: target = first ^ second.
    2. Initialize a flag found = false and a result array ans_i = [-1, -1].
    3. Iterate through possible substring lengths len from 1 to the length of s.
    4. For each len, iterate through all possible starting indices i from 0 to s.length() - len.
    5. Extract the substring sub = s.substring(i, i + len).
    6. Convert sub to its decimal value val. Be mindful of potential NumberFormatException for long substrings, although we only need to consider lengths up to about 31.
    7. If val equals target, we have found the shortest substring with the minimum left index due to the loop order. Set ans_i = [i, i + len - 1], set found = true, and break from all loops for the current query.
    8. If found is true, stop searching for the current query.
  • After checking all possibilities for a query, if no match was found, the answer remains [-1, -1].
  • Collect the answers for all queries and return them.

Walkthrough

This brute-force method directly translates the problem statement into a solution. For each of the Q queries, we determine the target decimal value. The core of the algorithm is a nested loop structure that generates all substrings of s. To meet the problem's criteria for the 'best' substring (shortest, then smallest starting index), we iterate on length len from 1 upwards. For a fixed len, we iterate on the starting position i from 0 upwards. This ensures that the first time we find a substring whose decimal value matches our target, it is guaranteed to be one of the shortest possible length, and among those, the one with the minimum starting index.

class Solution {    public int[][] substringXorQueries(String s, int[][] queries) {        int q = queries.length;        int n = s.length();        int[][] ans = new int[q][2];         for (int k = 0; k < q; k++) {            int first = queries[k][0];            int second = queries[k][1];            int target = first ^ second;                        int[] currentAns = {-1, -1};            int minLength = Integer.MAX_VALUE;             // Iterate through all substrings            for (int i = 0; i < n; i++) {                long currentVal = 0;                for (int j = i; j < n; j++) {                    // Optimization: limit substring length to avoid overflow and unnecessary work                    if (j - i + 1 > 32) break;                                        currentVal = (currentVal << 1) | (s.charAt(j) - '0');                                        if (currentVal == target) {                        int currentLength = j - i + 1;                        if (currentLength < minLength) {                            minLength = currentLength;                            currentAns[0] = i;                            currentAns[1] = j;                        }                         // The problem asks for min left for the same length.                        // A better loop structure is needed to avoid this check.                        // Iterating by length first is better.                    }                }            }            ans[k] = currentAns;        }        // The above code finds shortest, but not necessarily min-left first.        // A correct brute-force would be:        for (int k = 0; k < q; k++) {            int target = queries[k][0] ^ queries[k][1];            ans[k] = new int[]{-1, -1};            boolean found = false;            for (int len = 1; len <= n; len++) {                if (len > 32) break; // Optimization                for (int i = 0; i <= n - len; i++) {                    int j = i + len - 1;                    String sub = s.substring(i, j + 1);                    try {                        int val = Integer.parseInt(sub, 2);                        if (val == target) {                            ans[k][0] = i;                            ans[k][1] = j;                            found = true;                            break;                        }                    } catch (NumberFormatException e) { /* Value too large */ }                }                if (found) break;            }        }        return ans;    }}

Complexity

Time

O(Q * N * L), where Q is the number of queries, N is the length of `s`, and L is the maximum length of a relevant substring (approx. 31). For each query, we iterate through O(N * L) substrings, and converting each to an integer takes O(L). This results in a total time complexity that is too high for the given constraints.

Space

O(1) or O(Q) if we consider the space for the output array, where Q is the number of queries.

Trade-offs

Pros

  • Simple to conceptualize and implement.

  • Requires minimal extra space, only for storing the final answer.

Cons

  • Extremely inefficient and will not pass the time limits for the given constraints.

  • Repeatedly performs the same substring conversions across different queries.

Solutions

class Solution {public  int[][] substringXorQueries(String s, int[][] queries) {    Map<Integer, int[]> d = new HashMap<>();    int n = s.length();    for (int i = 0; i < n; ++i) {      int x = 0;      for (int j = 0; j < 32 && i + j < n; ++j) {        x = x << 1 | (s.charAt(i + j) - '0');        d.putIfAbsent(x, new int[]{i, i + j});        if (x == 0) {          break;        }      }    }    int m = queries.length;    int[][] ans = new int[m][2];    for (int i = 0; i < m; ++i) {      int first = queries[i][0], second = queries[i][1];      int val = first ^ second;      ans[i] = d.getOrDefault(val, new int[]{-1, -1});    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem