Problem
You are given a binary string s, and a 2D integer array queries where queries[i] = [firsti, secondi].
For the ith query, find the shortest substring of s whose decimal value, val, yields secondi when bitwise XORed with firsti. In other words, val ^ firsti == secondi.
The answer to the ith query is the endpoints (0-indexed) of the substring [lefti, righti] or [-1, -1] if no such substring exists. If there are multiple answers, choose the one with the minimum lefti.
Return an array ans where ans[i] = [lefti, righti] is the answer to the ith query.
A substring is a contiguous non-empty sequence of characters within a string.
Example 1:
Input: s = "101101", queries = [[0,5],[1,2]]
Output: [[0,2],[2,3]]
Explanation: For the first query the substring in range [0,2] is "101" which has a decimal value of 5, and 5 ^ 0 = 5, hence the answer to the first query is [0,2]. In the second query, the substring in range [2,3] is "11", and has a decimal value of 3, and 3 ^ 1 = 2. So, [2,3] is returned for the second query.
Example 2:
Input: s = "0101", queries = [[12,8]]
Output: [[-1,-1]]
Explanation: In this example there is no substring that answers the query, hence [-1,-1] is returned.
Example 3:
Input: s = "1", queries = [[4,5]]
Output: [[0,0]]
Explanation: For this example, the substring in range [0,0] has a decimal value of 1, and 1 ^ 4 = 5. So, the answer is [0,0].
Constraints:
1 <= s.length <= 104s[i]is either'0'or'1'.1 <= queries.length <= 1050 <= firsti, secondi <= 109
Solution (Java)
class Solution {
public int[][] substringXorQueries(String s, int[][] queries) {
int m = queries.length;
int[][] ret = new int[m][];
int n = s.length();
Map<Integer, int[]> map = new HashMap<>();
map.put(0, new int[]{s.indexOf("0"),s.indexOf("0")});
int[] not = new int[]{-1, -1};
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '0') continue;
for (int j = i + 1; j <= n; j++) {
String sub = s.substring(i, j);
if (sub.length() > Integer.toBinaryString(Integer.MAX_VALUE).length()) break;
// if (map.contains)
map.putIfAbsent(Integer.parseInt(sub, 2), new int[]{i, j - 1});
}
}
for (int i = 0; i < m; i++) {
int x = queries[i][0] ^ queries[i][1];
if (map.containsKey(x)) {
ret[i] = map.get(x);
} else {
ret[i] = not;
}
}
return ret;
}
}
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).