Leetcode 2564: Substring XOR Queries
You are given a binary string s and a 2D array of queries. Each query is represented as [firsti, secondi], where firsti and secondi are integers. For each query, you need to find the shortest substring of s whose decimal value XORed with firsti equals secondi.
In other words, find a substring whose decimal value, when XORed with firsti, results in secondi. If such a substring exists, return its starting and ending indices (0-indexed). If no such substring exists, return [-1, -1].
If there are multiple valid substrings, return the one with the smallest starting index.
Problem
Approach
Steps
Complexity
Input: You are given a binary string `s` and a list of queries where each query consists of two integers `firsti` and `secondi`.
Example: s = '101101', queries = [[0,5], [1,2]]
Constraints:
• 1 <= s.length <= 10^4
• 1 <= queries.length <= 10^5
• 0 <= firsti, secondi <= 10^9
Output: For each query, return the starting and ending indices of the shortest valid substring or [-1, -1] if no valid substring exists.
Example: Output: [[0,2], [2,3]]
Constraints:
• The output should be a list of pairs of integers where each pair corresponds to the indices of the valid substring or [-1, -1] if no valid substring is found.
Goal: To efficiently find the shortest valid substring for each query.
Steps:
• Convert the binary string into decimal values of substrings.
• For each query, calculate the XOR of `firsti` and `secondi` to get the target value.
• Check if the target value can be found as a decimal value of a substring of `s`.
• Return the indices of the substring if it exists, otherwise return [-1, -1].
Goal: The problem constraints are manageable for optimized solutions that leverage precomputation and binary search.
Steps:
• 1 <= s.length <= 10^4
• 1 <= queries.length <= 10^5
• 0 <= firsti, secondi <= 10^9
Assumptions:
• The input binary string is valid and consists only of '0' and '1'.
• The queries array contains valid integer pairs within the specified range.
• Input: Example 1:
• Explanation: Given the string s = '101101' and queries = [[0,5], [1,2]], we can find the following substrings:
For the first query, the substring '101' (indices 0 to 2) has a decimal value of 5, and 5 XOR 0 equals 5, so the answer is [0, 2].
For the second query, the substring '11' (indices 2 to 3) has a decimal value of 3, and 3 XOR 1 equals 2, so the answer is [2, 3].
• Input: Example 2:
• Explanation: Given the string s = '0101' and queries = [[12,8]], there is no substring whose decimal value XORed with 12 equals 8, so the answer is [-1, -1].
• Input: Example 3:
• Explanation: Given the string s = '1' and queries = [[4,5]], the substring '1' (indices 0 to 0) has a decimal value of 1, and 1 XOR 4 equals 5, so the answer is [0, 0].
Approach: The approach to solving this problem involves finding all possible substrings of the binary string and checking their decimal values. For each query, we can calculate the target XOR value and search for the substring whose decimal value matches the target.
Observations:
• The XOR operation is reversible, so for each query, we can calculate the target value by XORing the two integers.
• We need to efficiently search for substrings whose decimal values match the target.
• Precomputing all possible substrings and storing their decimal values can speed up the search for each query.
Steps:
• Convert the binary string into all possible substrings and calculate their decimal values.
• Store these substrings in a map with their decimal values as keys and their indices as values.
• For each query, calculate the target value and check if it exists in the map.
• Return the indices of the corresponding substring if found, otherwise return [-1, -1].
Empty Inputs:
• If the binary string is empty, the answer should be [-1, -1] for all queries.
Large Inputs:
• Ensure that the solution works efficiently even with large input sizes, such as strings of length up to 10^4 and up to 10^5 queries.
Special Values:
• Handle edge cases where the binary string contains only '0's or '1's.
Constraints:
• The solution should handle queries efficiently by leveraging preprocessing and fast search techniques.
string str(int n) {
string ans = "";
if(n == 0) return "0";
while(n) {
if(n & 1) {
ans = "1" + ans;
} else {
ans = "0" + ans;
}
n >>= 1;
}
return ans;
}
vector<int> substr(string m, string s) {
if(m.size() < s.size()) return vector<int>{-1, -1};
for(int i = 0; i < m.size(); i++) {
int j = 0;
while(j < s.size() && i + j < m.size() && m[i + j] == s[j]) j++;
if(j == s.size()) return vector<int>{i, i + j - 1};
}
return vector<int>{-1, -1};
}
vector<vector<int>> substringXorQueries(string m, vector<vector<int>>& q) {
int n = q.size();
map<int, vector<int>> mp;
int k = m.size();
for(int j = 0; j < k; j++) {
if(m[j] == '0') {
if(!mp.count(0)) mp[0] = {j, j};
continue;
}
int num = 0;
for(int i = j; i <= min(j + 31, k - 1); i++) {
num = (num << 1) + (m[i] - '0');
if(!mp.count(num)) mp[num] = {j, i};
}
}
vector<vector<int>> ans(n, vector<int>{-1, -1});
for(int i = 0; i < n; i++) {
int num = (q[i][0] ^ q[i][1]);
if(mp.count(num))
ans[i] = mp[num];
}
return ans;
}
1 : Function Definition
string str(int n) {
Function to convert an integer to its binary string representation.
2 : Variable Initialization
string ans = "";
Initializes an empty string to hold the binary result.
3 : Edge Case Handling
if(n == 0) return "0";
Handles the special case where the input number is zero by returning "0".
4 : Looping and Bitwise Operation
while(n) {
Iterates while n is not zero.
5 : Conditional Statement
if(n & 1) {
Checks if the least significant bit of n is 1.
6 : String Manipulation
ans = "1" + ans;
Adds '1' to the beginning of the binary result string.
7 : Else Condition
} else {
If the least significant bit is 0.
8 : String Manipulation
ans = "0" + ans;
Adds '0' to the beginning of the binary result string.
9 : Bitwise Operation
n >>= 1;
Right shifts n by 1 bit to process the next bit.
10 : Return Statement
return ans;
Returns the final binary string.
11 : Function Definition
vector<int> substr(string m, string s) {
Function to find the substring s in string m and return its indices.
12 : Edge Case Handling
if(m.size() < s.size()) return vector<int>{-1, -1};
Handles the case where s is longer than m.
13 : Looping
for(int i = 0; i < m.size(); i++) {
Loops through string m to search for substring s.
14 : Variable Initialization
int j = 0;
Initializes a counter for matching characters.
15 : Nested Loop
while(j < s.size() && i + j < m.size() && m[i + j] == s[j]) j++;
Checks if substring s matches a portion of m starting at index i.
16 : Conditional Statement
if(j == s.size()) return vector<int>{i, i + j - 1};
If the full substring s is found, return its indices.
17 : Return Statement
return vector<int>{-1, -1};
If the substring is not found, return [-1, -1].
18 : Function Definition
vector<vector<int>> substringXorQueries(string m, vector<vector<int>>& q) {
Function to solve multiple XOR substring queries on string m.
19 : Variable Initialization
int n = q.size();
Initializes the number of queries.
20 : Map Initialization
map<int, vector<int>> mp;
Creates a map to store results of XOR computations.
21 : Variable Initialization
int k = m.size();
Initializes the size of string m.
22 : Looping
for(int j = 0; j < k; j++) {
Loops through each character in string m.
23 : Conditional Statement
if(m[j] == '0') {
Checks if the character in m is '0'.
24 : Map Insertion
if(!mp.count(0)) mp[0] = {j, j};
Adds a mapping for the value '0'.
25 : Continue Statement
continue;
Continues to the next iteration if the character is '0'.
26 : Variable Initialization
int num = 0;
Initializes a variable to hold the current number.
27 : Nested Loop
for(int i = j; i <= min(j + 31, k - 1); i++) {
Loops through the next 32 bits or until the end of string m.
28 : Bitwise Operation
num = (num << 1) + (m[i] - '0');
Constructs the number by shifting bits and adding the current bit.
29 : Map Insertion
if(!mp.count(num)) mp[num] = {j, i};
Inserts the current number and its corresponding range into the map.
30 : Return Statement
vector<vector<int>> ans(n, vector<int>{-1, -1});
Initializes a result vector with default [-1, -1] values.
31 : Looping
for(int i = 0; i < n; i++) {
Iterates over all queries.
32 : Bitwise Operation
int num = (q[i][0] ^ q[i][1]);
Computes the XOR of the two query values.
33 : Map Lookup
if(mp.count(num))
Checks if the XOR result is present in the map.
34 : Return Statement
ans[i] = mp[num];
If found, updates the answer with the corresponding range.
35 : Return Statement
return ans;
Returns the final answer for all queries.
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n^2)
Description: The time complexity depends on preprocessing the binary string and the number of queries. The worst case occurs when checking all possible substrings for each query.
Best Case: O(n)
Worst Case: O(n^2)
Description: The space complexity is determined by the need to store all possible substrings and their decimal values.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus