# Jump Game VII
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/jump-game-vii)
Canonical: https://scaleengineer.com/dsa/problems/jump-game-vii
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** String
---
## Problem
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`

# Approaches
## Dynamic Programming
This approach uses dynamic programming to solve the problem. We define an array `dp` where `dp[i]` is `true` if index `i` is reachable from index 0, and `false` otherwise. To determine `dp[i]`, we check if `s[i]` is '0' and if there exists any previously reachable index `j` that can jump to `i`. A jump from `j` to `i` is valid if `i - maxJump <= j <= i - minJump`. This involves a nested loop, where the outer loop iterates through each index `i` and the inner loop checks the valid window of previous indices `j`.
**Time:** O(n * k), where n is the length of the string and k is `maxJump - minJump`. For each index `i`, we might scan up to `k` previous indices. In the worst case, `k` can be close to `n`, leading to an `O(n^2)` complexity. · **Space:** O(n), where n is the length of the string `s`. This is for the `dp` array used to store the reachability of each index.
**Pros:** It's a direct translation of the problem's recurrence relation, making it relatively easy to understand and implement.
**Cons:** The nested loop structure leads to a high time complexity, which will result in a 'Time Limit Exceeded' error on larger inputs.
### Explanation
In this approach, we build a boolean array `dp` of the same size as the input string `s`. `dp[i]` stores whether index `i` is reachable. We know `dp[0]` is `true` because we start there. For every other index `i` from 1 to `n-1`, we can determine its reachability based on the reachability of previous indices.

An index `i` is reachable if two conditions are met:
1.  The character at that index, `s[i]`, must be `'0'`. 
2.  There must be at least one reachable index `j` from which we can jump to `i`. The jump condition `j + minJump <= i <= j + maxJump` can be rearranged to find the range of `j` for a given `i`: `i - maxJump <= j <= i - minJump`.

So, for each `i`, we check if `s[i]` is `'0'`. If it is, we then scan the `dp` array in the range `[max(0, i - maxJump), i - minJump]` to see if any `dp[j]` is `true`. If we find one, we set `dp[i]` to `true` and move to the next index. The final answer is the value of `dp[s.length - 1]`.

```java
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;

        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == '0') {
                for (int j = Math.max(0, i - maxJump); j <= i - minJump; j++) {
                    if (dp[j]) {
                        dp[i] = true;
                        break;
                    }
                }
            }
        }

        return dp[n - 1];
    }
}
```
### Algorithm
*   Create a boolean array `dp` of size `n`, where `dp[i]` will be `true` if index `i` is reachable, and `false` otherwise.
*   Initialize `dp[0]` to `true` since we start at index 0.
*   Iterate through the string from `i = 1` to `n-1`.
*   For each index `i`, if `s[i]` is `'0'`, iterate through all possible previous indices `j` from which a jump to `i` is valid.
*   The valid range for a previous index `j` is `i - maxJump <= j <= i - minJump`.
*   If we find any `j` in this range for which `dp[j]` is `true`, it means we can reach `i`. We set `dp[i] = true` and can break the inner loop for the current `i`.
*   After iterating through all `i`, the value of `dp[n-1]` will tell us if the last index is reachable.

## DP with Sliding Window Count
This approach optimizes the naive DP solution by avoiding the inner loop. The key observation is that as we move from index `i` to `i+1`, the window of previous indices `[i - maxJump, i - minJump]` slides. Instead of re-scanning this window every time, we can maintain a count of reachable positions within it. We use a single variable, `reachableCount`, to track this. When the window slides, we update the count in O(1) time by adding the contribution of the index that enters the window and subtracting the contribution of the index that leaves.
**Time:** O(n). We iterate through the string once, and all operations inside the loop (updating count, checking conditions) are constant time. · **Space:** O(n), for the `dp` array. Although we optimize the time, we still need to store the reachability of all previous indices.
**Pros:** Achieves linear time complexity, which is efficient enough to pass for the given constraints.; The logic is a direct optimization of the DP approach and is relatively intuitive.
**Cons:** While the time complexity is optimal, this approach still requires O(n) extra space for the DP array.
### Explanation
The bottleneck in the previous DP approach is the repeated scanning of the window `[i - maxJump, i - minJump]`. We can optimize this by realizing that this is a sliding window problem. We can maintain a count of how many reachable positions (`dp[j] == true`) are in the current window.

Let's maintain a variable `reachableCount`. As we iterate `i` from 1 to `n-1`, `reachableCount` will store the number of reachable indices in the range `[i - maxJump, i - minJump]`. We can update this count in constant time. When we move from `i-1` to `i`, the index `i - minJump` enters the window's right side, and `i - maxJump - 1` leaves the window's left side. 

So, at each step `i`, we first update `reachableCount` based on `dp[i - minJump]` (entering) and `dp[i - maxJump - 1]` (leaving). Then, if `s[i] == '0'` and `reachableCount > 0`, we know `i` is reachable and set `dp[i] = true`. This process eliminates the inner loop, reducing the time complexity to linear.

```java
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 reachableCount = 0;

        for (int i = 1; i < n; i++) {
            if (i >= minJump) {
                if (dp[i - minJump]) {
                    reachableCount++;
                }
            }
            if (i > maxJump) {
                if (dp[i - maxJump - 1]) {
                    reachableCount--;
                }
            }

            if (s.charAt(i) == '0' && reachableCount > 0) {
                dp[i] = true;
            }
        }

        return dp[n - 1];
    }
}
```
### Algorithm
*   Create a boolean array `dp` of size `n`, with `dp[0] = true`.
*   Initialize a counter `reachableCount = 0`.
*   Iterate `i` from `1` to `n-1`.
*   At each `i`, update `reachableCount` based on the window `[i - maxJump, i - minJump]`. This window slides as `i` increases.
    *   If `i >= minJump` and `dp[i - minJump]` was reachable, it means a new potential jump position has entered our consideration window. Increment `reachableCount`.
    *   If `i > maxJump` and `dp[i - maxJump - 1]` was reachable, it means a position has just slid out of our consideration window. Decrement `reachableCount`.
*   If `s[i] == '0'` and `reachableCount > 0`, it means there's at least one valid position to jump from, so we set `dp[i] = true`.
*   Return `dp[n-1]` after the loop.

## Sliding Window with Deque
This approach provides the most optimal solution in terms of space complexity. Instead of using a full `dp` array to remember every reachable state, we only need to keep track of the reachable indices within the current sliding window. A deque is a perfect data structure for this. It will store the indices of reachable '0's. As we iterate through the string, we use the deque to find out in O(1) time if there's a valid position to jump from. We add newly found reachable indices to the back of the deque and remove indices that are too far from the front.
**Time:** O(n). Each index of the string is processed once. It is also added to and removed from the deque at most once, leading to amortized O(1) time for deque operations per index. · **Space:** O(maxJump). The deque stores indices within the sliding window. The difference between the maximum and minimum index in the deque is at most `maxJump`. Therefore, the size of the deque is bounded by `maxJump`.
**Pros:** Optimal time complexity of O(n).; Optimal space complexity, which is better than O(n) when `maxJump` is significantly smaller than `n`.
**Cons:** The logic involving the deque can be slightly more complex to grasp compared to the DP array-based solutions.
### Explanation
To optimize space, we can observe that we don't need to store the reachability of *all* past indices, only those that could potentially be used for future jumps. These are the reachable indices that fall within a sliding window.

A deque can efficiently manage this set of relevant reachable indices. We will store the indices `j` where `s[j] == '0'` and `j` is reachable.

As we iterate with `i` from `1` to `n-1`:
1.  **Slide the window:** We remove indices from the front of the deque that are no longer reachable because they are too far behind. Specifically, any index `j` in the deque where `j < i - maxJump` is removed.
2.  **Check for reachability:** After sliding, we look at the front of the deque. If the deque is not empty and its front element `j` satisfies `j <= i - minJump`, it means there is a valid reachable position from which we can jump to `i`.
3.  **Update:** If `s[i]` is `'0'` and the reachability check passes, we add `i` to the back of the deque, as it is now a new reachable position.

Finally, we check if `n-1` was ever added to the deque. The last element in the deque will be the furthest reachable index we found. If it's `n-1`, we've succeeded.

```java
import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public boolean canReach(String s, int minJump, int maxJump) {
        int n = s.length();
        if (s.charAt(n - 1) == '1') {
            return false;
        }

        Deque<Integer> queue = new LinkedList<>();
        queue.offer(0);

        for (int i = 1; i < n; i++) {
            // Prune indices that are too far
            while (!queue.isEmpty() && queue.peek() < i - maxJump) {
                queue.poll();
            }

            // Check if there's a valid jump position and s[i] is '0'
            if (!queue.isEmpty() && s.charAt(i) == '0') {
                int prevIndex = queue.peek();
                if (prevIndex <= i - minJump) {
                    queue.offer(i);
                }
            }
        }

        // The last index must be reachable
        return !queue.isEmpty() && queue.peekLast() == n - 1;
    }
}
```
### Algorithm
*   If `s[n-1]` is `'1'`, return `false` immediately.
*   Initialize a deque (double-ended queue) and add the starting index `0`.
*   Iterate `i` from `1` to `n-1`.
*   For each `i`, first prune the deque from the front. Remove any index `j` such that `j < i - maxJump`, as they are now too far to jump from.
*   After pruning, check the index at the front of the deque, `j = deque.front()`. If `j <= i - minJump`, it means there is a reachable position within the valid jump range `[i - maxJump, i - minJump]`.
*   If `s[i]` is `'0'` and the condition above is met, then index `i` is reachable. Add `i` to the back of the deque.
*   After the loop, the last index `n-1` is reachable if and only if it was added to the deque. This can be checked by seeing if the last element in the deque is `n-1`.

# Solutions
### Java

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

### JavaScript

```javascript
/** * @param {string} s * @param {number} minJump * @param {number} maxJump * @return {boolean} */ var canReach =
  function (s, minJump, maxJump) {
    const n = s.length;
    const pre = Array(n + 1).fill(0);
    pre[1] = 1;
    const f = Array(n).fill(false);
    f[0] = true;
    for (let i = 1; i < n; ++i) {
      if (s[i] === " 0 ") {
        const [l, r] = [Math.max(0, i - maxJump), i - minJump];
        f[i] = l <= r && pre[r + 1] - pre[l] > 0;
      }
      pre[i + 1] = pre[i] + (f[i] ? 1 : 0);
    }
    return f[n - 1];
  };

```

### CPP

```cpp
class Solution { public: bool canReach ( string s , int minJump , int maxJump ) { int n = s . size (); int pre [ n + 1 ]; memset ( pre , 0 , sizeof ( pre )); pre [ 1 ] = 1 ; bool f [ n ]; memset ( f , 0 , sizeof ( f )); f [ 0 ] = true ; for ( int i = 1 ; i < n ; ++ i ) { if ( s [ i ] == '0' ) { int l = max ( 0 , i - maxJump ); int r = i - minJump ; f [ i ] = l <= r && pre [ r + 1 ] - pre [ l ]; } pre [ i + 1 ] = pre [ i ] + f [ i ]; } return f [ n - 1 ]; } };
```

### Python

```python
class Solution : def canReach ( self , s : str , minJump : int , maxJump : int ) -> bool : n = len ( s ) pre = [ 0 ] * ( n + 1 ) pre [ 1 ] = 1 f = [ True ] + [ False ] * ( n - 1 ) for i in range ( 1 , n ): if s [ i ] == "0" : l , r = max ( 0 , i - maxJump ), i - minJump f [ i ] = l <= r and pre [ r + 1 ] - pre [ l ] > 0 pre [ i + 1 ] = pre [ i ] + f [ i ] return f [ - 1 ]
```