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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Substring XOR Queries

Difficulty: Medium

Problem Description

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 [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.

Key Insights

  • The problem requires finding substrings whose decimal values produce specific results when XORed with given integers.
  • The decimal value of a binary substring can be calculated as we progress through the string.
  • Efficient searching can be achieved using a combination of a hash map and two-pointer technique to minimize the time complexity.

Space and Time Complexity

Time Complexity: O(n * m), where n is the length of the binary string and m is the number of queries. In the worst case, checking each substring for each query. Space Complexity: O(m), for storing the results of queries.

Solution

The solution involves iterating through the binary string and calculating the decimal values of all possible substrings. For each substring, we check whether it meets the criteria defined by the queries using a hash map to store the values obtained from XOR operations. The two-pointer technique can help efficiently find the shortest substring that meets the query conditions.

Code Solutions

def substringXorQueries(s, queries):
    n = len(s)
    result = []
    value_to_indices = {}
    
    # Generate all substrings and their decimal values
    for start in range(n):
        num = 0
        for end in range(start, n):
            num = (num << 1) | (1 if s[end] == '1' else 0)
            if num not in value_to_indices:
                value_to_indices[num] = (start, end)
    
    for first, second in queries:
        target = first ^ second
        if target in value_to_indices:
            result.append(value_to_indices[target])
        else:
            result.append([-1, -1])
    
    return result
← Back to All Questions