Code Implementation

class Solution:
    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
        n = len(s)
        if s[-1] != '0':
            return False
        dp = [False] * n
        dp[0] = True
        pre = 0
        for i in range(1, n):
            if i - minJump >= 0:
                pre += dp[i - minJump]
            if i - maxJump - 1 >= 0:
                pre -= dp[i - maxJump - 1]
            dp[i] = pre > 0 and s[i] == '0'
        return dp[-1]
      

class Solution {
public:
    bool canReach(string s, int minJump, int maxJump) {
        int n = s.size();
        if (s[n-1] != '0') return false;
        vector<bool> dp(n, false);
        dp[0] = true;
        int pre = 0;
        for (int i = 1; i < n; ++i) {
            if (i - minJump >= 0) pre += dp[i - minJump];
            if (i - maxJump - 1 >= 0) pre -= dp[i - maxJump - 1];
            dp[i] = pre > 0 && s[i] == '0';
        }
        return dp[n-1];
    }
};
      

class Solution {
    public boolean canReach(String s, int minJump, int maxJump) {
        int n = s.length();
        if (s.charAt(n - 1) != '0') return false;
        boolean[] dp = new boolean[n];
        dp[0] = true;
        int pre = 0;
        for (int i = 1; i < n; i++) {
            if (i - minJump >= 0) pre += dp[i - minJump] ? 1 : 0;
            if (i - maxJump - 1 >= 0) pre -= dp[i - maxJump - 1] ? 1 : 0;
            dp[i] = pre > 0 && s.charAt(i) == '0';
        }
        return dp[n - 1];
    }
}
      

var canReach = function(s, minJump, maxJump) {
    const n = s.length;
    if (s[n-1] !== '0') return false;
    const dp = new Array(n).fill(false);
    dp[0] = true;
    let pre = 0;
    for (let i = 1; i < n; i++) {
        if (i - minJump >= 0) pre += dp[i - minJump] ? 1 : 0;
        if (i - maxJump - 1 >= 0) pre -= dp[i - maxJump - 1] ? 1 : 0;
        dp[i] = pre > 0 && s[i] === '0';
    }
    return dp[n-1];
};
      

Problem Description

Given a binary string s (composed of '0's and '1's), and two integers minJump and maxJump, you start at index 0 and want to reach the last index. From position i, you can jump to any index j such that i + minJump ≤ j ≤ i + maxJump and s[j] == '0'. You cannot land on or jump over indices with '1'. Return true if you can reach the last index, otherwise return false.

• You can only move forward.
• You cannot reuse elements or jump to any index more than once.
• There is only one valid path for each set of jumps; you may not skip over '1's.
• The input can be large, so efficiency is important.

Thought Process

At first, you might think of trying every possible jump from every '0' position, similar to a breadth-first search (BFS) or recursion. For each index, you could check all possible jumps in the range [minJump, maxJump] and see if you can eventually reach the end. However, this brute-force approach is inefficient for large strings because it would revisit the same positions multiple times, leading to a time complexity that is too high.

To optimize, we notice that we can use dynamic programming: for each position, we want to know if it's reachable from the start. But checking all previous reachable positions for each index is still too slow. Instead, we can keep a running count or window of reachable positions using prefix sums or a sliding window, which allows us to efficiently update which indices are reachable without redundant checks.

Solution Approach

• Step 1: Initialization
  Create an array (let's call it dp) of the same length as s. dp[i] will be true if index i is reachable, otherwise false. Set dp[0] to true since you always start at the first index.
• Step 2: Sliding Window Technique
  For each index i from 1 to the end:
  • We want to know if any index in the range [i - maxJump, i - minJump] is reachable (i.e., dp[j] == true for some j in that range), and s[i] is '0'.
  • To avoid checking every index in that range for every i, we maintain a running sum (call it pre) of reachable positions in the window.
  • When i - minJump enters the window, add dp[i - minJump] to pre. When i - maxJump - 1 leaves the window, subtract dp[i - maxJump - 1] from pre.
  • If pre > 0 and s[i] == '0', set dp[i] to true.
• Step 3: Final Check
  After processing all indices, return the value of dp[n-1] (where n is the length of s), indicating if the last index is reachable.

This approach is efficient because each index is processed in constant time, and we only keep track of a running sum rather than repeatedly scanning windows.

Example Walkthrough

Suppose s = "011010", minJump = 2, maxJump = 3.
Let's walk through each step:

• Index 0: Start here, dp[0]=true.
• Index 1: Can't jump here from 0 (need at least minJump=2), dp[1]=false.
• Index 2: Can jump from 0 (0+2=2), s[2]='1', so dp[2]=false.
• Index 3: Can jump from 0 (0+3=3), s[3]='0', so dp[3]=true.
• Index 4: Can jump from 1 (not reachable), 2 (not reachable), or 3 (reachable and 3+1=4), but minJump=2, so check 1 to 2 back. Only 2 is in range, but dp[2]=false. So dp[4]=false.
• Index 5: Can jump from 2 (not reachable), 3 (reachable), or 4 (not reachable). 3 is in range and dp[3]=true, s[5]='0', so dp[5]=true.

The last index (dp[5]) is true, so the answer is true.

Time and Space Complexity

• Brute Force Approach:
  For each index, you might check all previous indices within the jump range, leading to O(n * maxJump) time complexity, which is not efficient for large inputs.
• Optimized Approach:
  Using the sliding window and prefix sum trick, each index is processed in O(1) time. So the total time complexity is O(n).
  Space complexity is O(n) for the dp array.

Summary

The key insight is to avoid redundant work by using dynamic programming with a sliding window. Rather than checking every possible path, we only track which positions are reachable and efficiently update this information as we scan the string. This leads to a linear time solution, making it suitable for large inputs. The use of prefix sums or a running window is what makes this solution both elegant and efficient.