LeetCode 2564: Substring XOR Queries Solution

Master LeetCode problem 2564 (Substring XOR Queries), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2564. Substring XOR Queries

Medium

Array Hash Table String Bit Manipulation

Problem Explanation

Explanation:

To solve this problem, we can use a prefix XOR technique along with a hashmap to store the indices of each prefix XOR value encountered. We iterate through the string s to calculate the prefix XOR values at each position. Then, for each query, we check if there exists a prefix XOR value val such that val ^ firsti = secondi in the hashmap. If found, we update the answer with the shortest valid substring.

Algorithmic Idea:
1. Create a hashmap to store the indices of each prefix XOR value encountered.
2. Iterate through the string s and calculate the prefix XOR values at each position.
3. For each query, check if there exists a prefix XOR value val such that val ^ firsti = secondi in the hashmap.
4. Update the answer with the shortest valid substring.
Time Complexity: O(N) where N is the length of the string s.
Space Complexity: O(N) to store the prefix XOR values in the hashmap.

Solution Code

class Solution {
    public int[][] findSubstrings(String s, int[][] queries) {
        int n = s.length();
        int[] prefixXor = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixXor[i + 1] = prefixXor[i] ^ (s.charAt(i) - '0');
        }
        
        Map<Integer, Integer> map = new HashMap<>();
        int[][] ans = new int[queries.length][2];
        
        for (int i = 0; i < n; i++) {
            if (!map.containsKey(prefixXor[i])) {
                map.put(prefixXor[i], i);
            }
        }
        
        for (int i = 0; i < queries.length; i++) {
            int left = -1, right = n;
            int first = queries[i][0];
            int second = queries[i][1];
            for (int j = 0; j <= n; j++) {
                if (map.containsKey(prefixXor[j] ^ first)) {
                    int start = map.get(prefixXor[j] ^ first);
                    if (j - start < right - left) {
                        left = start;
                        right = j;
                    }
                }
            }
            ans[i][0] = left;
            ans[i][1] = right - 1;
        }
        
        return ans;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2564 (Substring XOR Queries)?

This page provides optimized solutions for LeetCode problem 2564 (Substring XOR Queries) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2564 (Substring XOR Queries)?

The time complexity for LeetCode 2564 (Substring XOR Queries) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2564 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2564 in Java, C++, or Python.

Back to LeetCode Solutions