Substring xor queries

Array Hash Table String Bit Manipulation

35.4% acceptance

Feb 25, 2026

404

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn substring_xor_queries(s: String, queries: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    use std::collections::HashMap;
    let s = s.as_bytes();
    let n = s.len();
    // Precompute: value -> [leftmost_start, end] (shortest then leftmost)
    let mut map: HashMap<i32, [i32; 2]> = HashMap::new();

    // Handle value 0: find leftmost '0'
    for i in 0..n {
      if s[i] == b'0' {
        map.insert(0, [i as i32, i as i32]);
        break;
      }
    }

    // Handle nonzero values: substrings starting with '1', length 1..=30
    for i in 0..n {
      if s[i] != b'1' { continue; }
      let mut val: i64 = 0;
      for len in 0..30usize.min(n - i) {
        val = (val << 1) | (s[i + len] - b'0') as i64;
        if val >= (1i64 << 30) { break; }
        map.entry(val as i32).or_insert([i as i32, (i + len) as i32]);
        // or_insert keeps the first (leftmost, shortest) occurrence
      }
    }

    queries.iter().map(|q| {
      let target = q[0] ^ q[1];
      if let Some(&ans) = map.get(&target) {
        ans.to_vec()
      } else {
        vec![-1, -1]
      }
    }).collect()
  }
}