Jump Game VII

Problem 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)
• s[j] == '0'

Return true if you can reach index s.length - 1 in s, or false otherwise.

Examples

Constraints

• 2 ≤ s.length ≤ 10⁵
• s[i] is either '0' or '1'.
• s[0] == '0'
• 1 ≤ minJump ≤ maxJump < s.length

Sliding Window Dynamic Programming

Let dp[i] be true if index i is reachable from the start. For index i to be reachable:

• s[i] == '0'
• There exists some previous reachable index j in the window [i - maxJump, i - minJump] such that dp[j] == true.

To check this window constraint in O(1) time rather than O(maxJump - minJump), we maintain a sliding window count of reachable indices.

• Let reachableCount be the number of reachable indices j inside the current window [i - maxJump, i - minJump].
• As we increment i:
  • Slide the right edge into the window: if i - minJump >= 0 and dp[i - minJump] is true, increment reachableCount.
  • Slide the left edge out of the window: if i - maxJump - 1 >= 0 and dp[i - maxJump - 1] is true, decrement reachableCount.
• If s[i] == '0' and reachableCount > 0, then dp[i] = true.

Solution: Sliding Window DP

class Solution {
    public boolean canReach(String s, int minJump, int maxJump) {
        int n = s.length();
        if (s.charAt(n - 1) == '1') return false;

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

        int reachableCount = 0;

        for (int i = 1; i < n; i++) {
            // add new candidate to window: i - minJump
            if (i >= minJump && dp[i - minJump]) {
                reachableCount++;
            }
            // remove expired candidate from window: i - maxJump - 1
            if (i > maxJump && dp[i - maxJump - 1]) {
                reachableCount--;
            }

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

        return dp[n - 1];
    }
}

class Solution:
    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
        n = len(s)
        if s[-1] == '1':
            return False

        dp = [False] * n
        dp[0] = True
        
        reachable_count = 0

        for i in range(1, n):
            # add new candidate entering window
            if i >= minJump and dp[i - minJump]:
                reachable_count += 1
            # remove old candidate exiting window
            if i > maxJump and dp[i - maxJump - 1]:
                reachable_count -= 1

            if s[i] == '0' and reachable_count > 0:
                dp[i] = True

        return dp[-1]

#include <string>
#include <vector>

class Solution {
public:
    bool canReach(std::string s, int minJump, int maxJump) {
        int n = s.length();
        if (s[n - 1] == '1') return false;

        std::vector<bool> dp(n, false);
        dp[0] = true;

        int reachableCount = 0;

        for (int i = 1; i < n; i++) {
            if (i >= minJump && dp[i - minJump]) {
                reachableCount++;
            }
            if (i > maxJump && dp[i - maxJump - 1]) {
                reachableCount--;
            }

            if (s[i] == '0' && reachableCount > 0) {
                dp[i] = true;
            }
        }

        return dp[n - 1];
    }
};

Complexity Analysis:

• Time Complexity: O(N) where N is the length of string s.
• Space Complexity: O(N) to store the DP array.

← All Problems