365. Jump Game VII

dp[i] is reachable if s[i]=='0' AND some already-reachable index sits in the window [i-maxJump, i-minJump]. Checking 'any reachable in a window' fast is a prefix-sum (or sliding-count) over the dp array — O(1) per position.

Reachability with a windowed OR

Mark dp[i] = true if index i is reachable. Index i is reachable when:

1. s[i] == '0' (you may stand there), and
2. at least one reachable index j lies in [i - maxJump, i - minJump] (you could jump from it).

The base case is dp[0] = true (given s[0] == '0').

Making the window check O(1)

"Is any dp[j] true in a window?" is a range-sum question. Keep a prefix sum pre of the boolean dp (treating true as 1). Then the count of reachable indices in [lo, hi] is pre[hi+1] - pre[lo], and it's positive exactly when some reachable index is in range:

for i in 1..n-1:
    if s[i] == '0':
        lo = max(0, i - maxJump); hi = i - minJump
        if hi >= lo and pre[hi+1] - pre[lo] > 0: dp[i] = true
    pre[i+1] = pre[i] + dp[i]
return dp[n-1]

(If s[n-1] == '1' the answer is immediately false.)

Worked example

s = "011010", minJump = 2, maxJump = 3.

• dp[0] = true.
• i=1..2: s[1]='1' skip; i=2 s[2]='1' skip.
• i=3: s[3]='0', window [0, 1], contains reachable 0 → dp[3] = true.
• i=4: s[4]='1' skip.
• i=5: s[5]='0', window [2, 3], contains reachable 3 → dp[5] = true.

dp[5] = true → reachable. Return true.

Complexity

• Time: O(n).
• Space: O(n) for the prefix sums (reducible to O(1) with a running window count).

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