{x}
blog image

Jump Game VII

You are 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.

 

Example 1:

Input: s = "011010", minJump = 2, maxJump = 3
Output: true
Explanation:
In the first step, move from index 0 to index 3. 
In the second step, move from index 3 to index 5.

Example 2:

Input: s = "01101110", minJump = 2, maxJump = 3
Output: false

 

Constraints:

  • 2 <= s.length <= 105
  • s[i] is either '0' or '1'.
  • s[0] == '0'
  • 1 <= minJump <= maxJump < s.length

Solution Explanation: Jump Game VII

This problem asks whether we can reach the end of a binary string s by jumping from index 0, where each jump's length is within the range [minJump, maxJump], and only landing on '0's.

Approach: Dynamic Programming with Prefix Sum Optimization

The solution utilizes dynamic programming to track reachability. A boolean array f stores whether each index is reachable. A prefix sum array pre efficiently determines if any reachable indices exist within a jump's range.

1. Initialization:

  • f[0] = True: The starting position (index 0) is always reachable.
  • pre[1] = 1: The prefix sum array indicates one reachable position (index 0) initially.

2. Iteration:

  • The code iterates through the string s from index 1 to n-1 (where n is the length of s).
  • For each index i:
    • If s[i] == '0' (the position is a valid landing spot):
      • It calculates the range of possible previous positions [l, r] from where we could have jumped to i (l = max(0, i - maxJump), r = i - minJump).
      • f[i] becomes True if and only if at least one reachable position exists within that range (pre[r+1] - pre[l] > 0). The prefix sum efficiently counts reachable positions in this range.
    • pre[i+1] is updated by adding 1 if f[i] is True, otherwise it remains the same as pre[i]. This maintains the prefix sum of reachable indices.

3. Result:

  • The function returns f[n-1], indicating whether the last index is reachable.

Time and Space Complexity Analysis

  • Time Complexity: O(n), where n is the length of the string s. The code iterates through the string once. Prefix sum calculations are O(1) per index.

  • Space Complexity: O(n). The boolean array f and the prefix sum array pre both have a size proportional to the length of the string.

Code Examples (Python):

class Solution:
    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
        n = len(s)
        pre = [0] * (n + 1)
        pre[1] = 1  # Initialize prefix sum
        f = [True] + [False] * (n - 1)  # Initialize reachability array
 
        for i in range(1, n):
            if s[i] == "0":  # Check if current index is valid to land
                l, r = max(0, i - maxJump), i - minJump  # Calculate jump range
                f[i] = l <= r and pre[r + 1] - pre[l] > 0  # Check reachability within range
            pre[i + 1] = pre[i] + f[i]  # Update prefix sum
 
        return f[-1]  # Return reachability of the last index

The other language examples provided earlier follow the same logic and algorithmic structure, differing only in syntax. The core idea remains consistent across all languages.