Ctrl K

Code Lookup in a Bit String

Medium
You are given a string bits made of 0 and 1 characters and a list requests, where each request is a pair [key, code]. For a request, find a contiguous piece of bits that, read as a binary number v, satisfies v XOR key == code. Among all matching pieces, pick the shortest one, and among equally short ones the one that starts furthest left. The answer to the request is the pair of its start and end indices [left, right] (0-based, both inclusive), or [-1, -1] if no such piece exists. Return the answers to all requests in their original order.
Example 1
bits="0110", requests=[[2, 4], [7, 7], [1, 0]] → [[1, 3], [0, 0], [1, 1]]

2 XOR 4 = 6, which is "110", the piece [1, 3]. 7 XOR 7 = 0, which is "0", the piece [0, 0]. 1 XOR 0 = 1, and the first 1 sits at position 1, giving [1, 1].

Example 2
bits="111", requests=[[3, 1], [0, 8]] → [[-1, -1], [-1, -1]]

3 XOR 1 = 2, which is "10", but the string has no 0. 0 XOR 8 = 8, which is "1000", also absent. Both answers are [-1, -1].

Constraints
  • 1 ≤ len(bits) ≤ 10⁴
  • Every character of bits is 0 or 1
  • 1 ≤ len(requests) ≤ 10⁵
  • 0 ≤ key, code ≤ 10⁹
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsPalindrome After a Few Fixes MediumOne New Letter MediumWords That Fit Each Puzzle HardWords From Working Keys EasySwapped Initials Names Hard
loading Python…
Input
bits="0110", requests=[[2, 4], [7, 7], [1, 0]]
Expected
[[1, 3], [0, 0], [1, 1]]

Run checks the first 3 tests in your browser. Submit checks all 102 tests on the server, hidden ones included.