##### Welcome to Subscribe On Youtube

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

# 1871. Jump Game VII

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'
• 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')
}
int size = indices.size();
boolean[] visited = new boolean[size];
visited = 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];
}
}

• // OJ: https://leetcode.com/problems/jump-game-vii/
// Time: O(N)
// Space: O(maxJump - minJump)
class Solution {
public:
bool canReach(string s, int minJump, int maxJump) {
if (s.back() == '1') return false;
queue<int> q;
int j = 0, prev = 0;
for (int i = 1; i < s.size(); ++i) {
if (i - prev > maxJump) return false;
if (s[i] == '1') continue;
j = max(j, i - maxJump);
while (i - j >= minJump) {
if (s[j] == '0') q.push(j);
++j;
}
while (q.size() && i - q.front() > maxJump) q.pop();
if (q.empty()) s[i] = '1'; // mark this position as non-reachable.
else prev = i;
}
return q.size();
}
};

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

############

# 1871. Jump Game VII
# https://leetcode.com/problems/jump-game-vii

class Solution:
def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
n = len(s)
visited, mx = set(), 0
queue = collections.deque()

while queue:
i = queue.popleft()

for j in range(max(i + minJump, mx + 1), min(i + maxJump + 1, n)):
if s[j] == "0" and j not in visited:
if j == n - 1: return True
queue.append(j)