Problem Statement in English

You’re given a 0-indexed binary string s and two integers minJump and maxJump. In the beginning, you are standing at index 0, which is equal to '0'. You can move from index i to index j if the following conditions are fulfilled:

  • i + minJump <= j <= min(i + maxJump, s.length - 1), and
  • s[j] == '0'.

Return true if you can reach index s.length - 1 in s, or false otherwise.

Approach

We can use a breadth first search (BFS) approach to solve this problem.

We start from index 0 and explore all the indices that we can jump to from there. We keep track of the farthest index we have reached so far to avoid unnecessary jumps.

We use a queue to keep track of the indices we need to explore. For each index, we calculate the range of indices we can jump to and add them to the queue if they are valid (i.e., they are within the bounds of the string and they are equal to ‘0’).

If we reach the last index of the string, we return true. If we exhaust the queue without reaching the last index, we return false.

And we’re done!

Solution in Python


class Solution:
    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
        n = len(s)
        far = 0
        q = deque([0])

        while q:
            index = q.popleft()
            
            start = max(far + 1, index + minJump)
            end = min(n, index + maxJump + 1)

            for i in range(start, end):
                if s[i] == "0":
                    if i == n - 1: return True
                    q.append(i)
                
            far = max(far, index + maxJump)

        return False

Complexity

  • Time: $O(n \cdot maxJump)$
    In the worst case, we might have to explore all the indices in the string and for each index, we might have to check up to maxJump indices.

  • Space: $O(n)$
    In the worst case, we might have to store all the indices in the queue.

Mistakes I Made

I tried using a set to track the indices we have visited 🤦‍♂️

And we are done.