Formatted question description: https://leetcode.ca/all/1871.html

# 1871. Jump Game VII

## Level

Medium

## Description

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 <= 10^5`

`s[i]`

is either`'0'`

or`'1'`

.`s[0] == '0'`

`1 <= minJump <= maxJump < s.length`

## Solution

Use a list to store the indices that have characters ‘0’ in `s`

. Then use two pointers `curr`

and `next`

to mark the indices that can be reached. Initially, index 0 can be reached and `curr = 0`

. For each `curr`

, find the range of `next`

such that `curr + minJump <= next <= curr + maxJump`

and `next < s.length()`

. Since both `curr`

and `next`

can only move forward, the two pointers can only loop over all indices once. Finally, return `true`

if and only if the index `s.length() - 1`

can be reached.

```
class Solution {
public boolean canReach(String s, int minJump, int maxJump) {
List<Integer> indices = new ArrayList<Integer>();
int length = s.length();
if (s.charAt(length - 1) != '0')
return false;
for (int i = 0; i < length; i++) {
if (s.charAt(i) == '0')
indices.add(i);
}
int size = indices.size();
boolean[] visited = new boolean[size];
visited[0] = true;
int curr = 0, next = 0;
while (curr < size) {
while (curr < size && !visited[curr])
curr++;
if (curr == size)
return false;
int currIndex = indices.get(curr);
while (next < size && indices.get(next) - currIndex < minJump)
next++;
while (next < size && indices.get(next) - currIndex <= maxJump) {
visited[next] = true;
next++;
}
curr++;
}
return visited[size - 1];
}
}
```