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];
}
}
{"ft_lang_label":"__label__en","ft_lang_prob":0.6405081,"math_prob":0.99549705,"size":2064,"snap":"2022-05-2022-21","text_gpt3_token_len":608,"char_repetition_ratio":0.1330097,"word_repetition_ratio":0.03794038,"special_character_ratio":0.33381784,"punctuation_ratio":0.18414919,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9956966,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-05-17T18:19:34Z\",\"WARC-Record-ID\":\"<urn:uuid:ba0ce17d-afa4-4ebf-a883-b102aa71f2a9>\",\"Content-Length\":\"27473\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:c02e81f0-3816-459f-bf5c-df406cb9a607>\",\"WARC-Concurrent-To\":\"<urn:uuid:e5cd6272-841e-4ae6-b492-c815622934ac>\",\"WARC-IP-Address\":\"99.86.224.36\",\"WARC-Target-URI\":\"https://leetcode.ca/2021-07-18-1871-Jump-Game-VII/\",\"WARC-Payload-Digest\":\"sha1:FPBPFKJZKIXU6BHSDQBAV565JE3ZDVBE\",\"WARC-Block-Digest\":\"sha1:5IAMWCO6X22WWIPQUKOFVZ56THM2WXDO\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-21/CC-MAIN-2022-21_segments_1652662519037.11_warc_CC-MAIN-20220517162558-20220517192558-00185.warc.gz\"}"}