LeetCode in Kotlin

2564. Substring XOR Queries

Medium

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 <= 104
• s[i] is either '0' or '1'.
• 1 <= queries.length <= 105
• 0 <= firsti, secondi <= 109

Solution

class Solution {
    fun substringXorQueries(s: String, queries: Array<IntArray>): Array<IntArray> {
        val n = s.length
        val indices = queries.withIndex().groupBy(
            keySelector = { it.value[0] xor it.value[1] },
            valueTransform = { it.index }
        ).toMutableMap()
        val res = Array(queries.size) { IntArray(2) { -1 } }
        fun helper(value: Int, left: Int, right: Int) {
            (indices.remove(value) ?: return).forEach {
                res[it][0] = left
                res[it][1] = right
            }
        }
        for (i in 0 until n) {
            if (s[i] == '0') {
                helper(0, i, i)
            } else {
                var tmp = 0L
                for (j in i until n) {
                    tmp = (tmp shl 1) + (s[j] - '0')
                    if (tmp > Int.MAX_VALUE) break
                    helper(tmp.toInt(), i, j)
                }
            }
        }
        return res
    }
}

This site is open source. Improve this page.