Jump Game VII

The key idea

Index i is reachable only if some already-reachable index j sits in the window [i - maxJump, i - minJump] AND s[i] == '0'. Instead of re-scanning that whole window for every i, keep a running count of reachable cells inside the sliding window — turning an O(n*k) scan into one O(n) pass.

Problem

You start standing at index 0 of a binary string s of length n. From index i you may jump to any index j such that i + minJump <= j <= min(i + maxJump, n - 1) and s[j] == '0'. You may only ever stand on a cell whose character is '0' (index 0 is guaranteed to be '0'). Return true if you can reach the last index n - 1, and false otherwise.

Constraints

2 <= s.length <= 10^5
s[i] is either '0' or '1'
s[0] == '0'
1 <= minJump <= maxJump < s.length

Examples

Input: s = "011010", minJump = 2, maxJump = 3 Output: true

Input: s = "01101110", minJump = 2, maxJump = 3 Output: false

Complexity

Time: O(n) Space: O(n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →