We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Substring XOR Queries

Number: 2700

Difficulty: Medium

Paid? No

Companies: Trilogy

Problem Description

Given a binary string s and an array of queries where each query is of the form [first, second], we need to find for each query the shortest substring of s whose decimal interpretation, when XORed with first, equals second. That is, if the decimal value of the substring is val, then it must satisfy val ^ first = second. If multiple valid substrings exist, return the one with the smallest left index; if none exist, return [-1, -1].

Key Insights

  • We can transform the query requirement to: find a substring whose decimal value val is equal to target where target = first ^ second.
  • The maximum target is 10^9, so its binary representation uses at most 30 bits. Therefore, when scanning s, we only need to consider substrings with length up to 31.
  • Precompute and map each possible substring value (obtained from s) along with its earliest occurrence (with minimal left) in s.
  • For substrings that start with '0', only the single-character substring "0" should be considered in order to avoid duplicates and to guarantee the shortest substring.
  • After building the mapping from value to its (left, right) indices, answer each query by checking if target exists in the map.

Space and Time Complexity

Time Complexity: O(n * L + Q) where n is length of s, L is at most 31 (the maximum substring length processed per index), and Q is the number of queries. Space Complexity: O(n * L) for the dictionary storing candidate substrings, which is acceptable given the constraints.

Solution

We precompute a dictionary mapping each possible substring’s decimal value to its earliest occurrence [left, right] from the string s. For each starting index i, we iterate j from i to min(i + 31, n) and update the running value. We skip extended substrings that start with '0' (after processing the single '0') since they would not be minimal. Once the map is built, each query [first, second] is answered by computing target = first XOR second and looking up the result in our mapping. If found, return the stored indices; otherwise return [-1, -1].

Code Solutions

# Python solution for Substring XOR Queries

class Solution:
    def substringXorQueries(self, s, queries):
        n = len(s)
        # Dict to store mapping from integer value to (left, right) of earliest occurrence
        substring_map = {}
        
        # Loop through each starting index in s
        for left in range(n):
            # If s[left] is '0', then only consider the substring "0".
            if s[left] == '0':
                # Only update if we haven't stored a substring for value 0 yet.
                if 0 not in substring_map:
                    substring_map[0] = [left, left]
                # Continue to next starting index to avoid processing longer substrings starting with '0'
                continue
            
            num = 0
            # Consider substrings up to length 31 (or until end of string)
            for right in range(left, min(n, left + 31)):
                num = num * 2 + (1 if s[right] == '1' else 0)
                # Only update if the value hasn't been set before (ensuring the minimal left index)
                if num not in substring_map:
                    substring_map[num] = [left, right]
                    
        # Process each query using the precomputed mapping
        result = []
        for first, second in queries:
            target = first ^ second
            if target in substring_map:
                result.append(substring_map[target])
            else:
                result.append([-1, -1])
        return result

# Example usage:
# s = "101101"
# queries = [[0,5],[1,2]]
# sol = Solution()
# print(sol.substringXorQueries(s, queries))
← Back to All Questions