Jump game vii

String Dynamic Programming Sliding Window Prefix Sum

26.4% acceptance

Mar 1, 2026

1804

120

You are given a 0-indexed binary string s and two integers minJump and maxJump. In the beginning, you are standing at index 0 ('0'). You can move from index i to index j if 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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn can_reach(s: String, min_jump: i32, max_jump: i32) -> bool {
    let bytes = s.as_bytes();
    let n = bytes.len();
    let min_j = min_jump as usize;
    let max_j = max_jump as usize;
    let mut reachable = vec![false; n];
    reachable[0] = true;
    // prefix sum of reachable
    let mut prefix = vec![0i32; n + 1];
    prefix[1] = 1;

    for j in 1..n {
      if bytes[j] == b'0' && j >= min_j {
        // Check if any reachable index in [j-maxJump, j-minJump] exists
        let lo = if j >= max_j { j - max_j } else { 0 };
        let hi = j - min_j;
        let count = prefix[hi + 1] - prefix[lo];
        if count > 0 {
          reachable[j] = true;
        }
      }
      prefix[j + 1] = prefix[j] + reachable[j] as i32;
    }

    reachable[n - 1]
  }
}