Jump Game VII
Medium · Greedy · String · Dynamic Programming · Sliding Window · Prefix Sum
Problem
You are given a binary string s and two integers minJump and maxJump. You start at index 0, and s[0] is always '0'.
From index i you may move to index j when both hold:
- i + minJump <= j <= min(i + maxJump, len(s) - 1), and
- s[j] == '0'.
Return true if you can reach index len(s) - 1, otherwise false.
Examples
Input: s = "0100100", minJump = 2, maxJump = 3 Output: true
Move 0 -> 3 -> 6, landing on 0 both times.
Input: s = "01110", minJump = 1, maxJump = 2 Output: false
From index 0 you can only reach indices 1 and 2, and both are 1.
Input: s = "000", minJump = 2, maxJump = 2 Output: true
One jump of exactly 2 reaches the end.
Constraints
- 2 <= len(s) <= 10^5
- s[i] is '0' or '1'
- s[0] == '0'
- 1 <= minJump <= maxJump < len(s)
Approaches
- Baseline: mark forward from every reachable index — time O(n · (maxJump - minJump)), space O(n)
Follow-up
How many jumps does it take at least? Breadth-first search answers that, and remembering how far you have already scanned keeps it linear, because indices leave the queue in increasing order. The first use case below asks exactly that.
Related problems
Start free on Cariara · Coding problems · System design studio
