Substring Xor Queries - Leetcode Solution

Problem statement:

Given a string s and an array queries where queries[i] = [starti, endi], find the XOR of all elements of s.substring(starti, endi + 1) interpreted as a binary number.

Solution:

We can use some pre-processing of the string s to calculate the prefix XORs and then use them to calculate the XOR of any substring. Let's define prefixXor[i] as the XOR of all characters in s from 0 to i. Then the XOR of a substring s.substring(starti, endi + 1) can be calculated as (prefixXor[starti-1] XOR prefixXor[endi]).

To calculate the prefix XORs, we can iterate over the string s and calculate prefixXor[i] using the formula: prefixXor[i] = prefixXor[i-1] XOR s[i] for i > 0 and prefixXor[0] = s[0]. Then we can use these prefix XORs to answer the queries in a loop.

Code:

Here is the Python code for the solution:

class Solution:
    def xorQueries(self, s: str, queries: List[List[int]]) -> List[int]:
        n = len(s)
        prefixXor = [0]*n
        prefixXor[0] = ord(s[0])
        for i in range(1, n):
            prefixXor[i] = prefixXor[i-1] ^ ord(s[i])

        res = []
        for starti, endi in queries:
            res.append(prefixXor[starti-1] ^ prefixXor[endi])

        return res

Time Complexity: O(n+Q), where n is the length of the string s and Q is the number of queries.

Space Complexity: O(n), for storing the prefix XORs.

Note: This solution assumes that the characters in the string s are ASCII characters. If the characters are Unicode characters, we need to use a different way to calculate the XOR of two characters.

1