Jump Game VII

🎯 Problem

You are given:

• A binary string s
• Two integers:
  • minJump
  • maxJump

You start from index 0.

You can jump from index i to index j if:

i + minJump <= j <= i + maxJump

and

s[j] == '0'

Return:

• true → if you can reach last index
• false → otherwise

🧠 Main Idea

For every position:

We only need to know:

"Is there ANY reachable index from which I can jump here?"

If YES:

• current index also becomes reachable

❌ Brute Force

For every index:

• check all previous positions
• see if any one can reach current index

This becomes slow.

✅ Better Idea

We use:

dp[i]

Meaning:

Can we reach index i ?

🔥 Important Observation

Suppose we are at index:

i

Then valid previous positions are:

[i - maxJump  ...  i - minJump]

If ANY index inside this range is reachable:

Then current index is also reachable.

✅ Sliding Window Trick

Instead of checking whole range every time:

We maintain:

reachableCount

Meaning:

How many reachable indices currently exist inside valid range

📌 Simple Working

As window moves:

Add New Index

When new index enters range:

i - minJump

If reachable:

reachableCount++

Remove Old Index

When old index leaves range:

i - maxJump - 1

If reachable:

reachableCount--

✅ Current Index Reachable?

If:

reachableCount > 0

AND

s[i] == '0'

Then:

dp[i] = true

🪜 Example

Input

s = "011010"
minJump = 2
maxJump = 3

Step 1

Start:

dp = [T, F, F, F, F, F]

Step 2 → i = 2

Valid previous range:

[0 ... 0]

Index 0 reachable ✅

But:

s[2] = '1'

So cannot stand here.

Step 3 → i = 3

Valid range:

[0 ... 1]

Index 0 reachable ✅

And:

s[3] = '0'

So:

dp[3] = true

Step 4 → i = 5

Valid range:

[2 ... 3]

Index 3 reachable ✅

And:

s[5] = '0'

So:

dp[5] = true

Reached end 🎉

✅ Final DP

[T, F, F, T, F, T]

Answer:

true

✅ Java Solution

class Main {

    public static boolean canReach(String s, int minJump, int maxJump) {

        int n = s.length();

        boolean[] dp = new boolean[n];
        dp[0] = true;

        int reachableCount = 0;

        for (int i = 1; i < n; i++) {

            // Add new reachable index into window
            if (i - minJump >= 0 && dp[i - minJump]) {
                reachableCount++;
            }

            // Remove old index from window
            if (i - maxJump - 1 >= 0 && dp[i - maxJump - 1]) {
                reachableCount--;
            }

            // Current position reachable
            if (s.charAt(i) == '0' && reachableCount > 0) {
                dp[i] = true;
            }
        }

        return dp[n - 1];
    }

    public static void main(String[] args) {

        String s = "011010";
        int minJump = 2;
        int maxJump = 3;

        System.out.println(
            canReach(s, minJump, maxJump)
        );
    }
}

⏱️ Time Complexity

O(N)

Because every index is processed once.

💾 Space Complexity

O(N)

For DP array.