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 &lt;= j &lt;= 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.

&nbsp;
Example 1:

Input: s = "011010", minJump = 2, maxJump = 3
Output: true
Explanation:
In the first step, move from index 0 to index 3. 
In the second step, move from index 3 to index 5.


Example 2:

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


&nbsp;
Constraints:


	2 &lt;= s.length &lt;= 105
	s[i] is either '0' or '1'.
	s[0] == '0'
	1 &lt;= minJump &lt;= maxJump &lt; s.length


class Solution:
    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
		# dp[i] represents whether i is reachable
        dp = [False for _ in s]
        dp[0] = True

        for i in range(1, len(s)):
            if s[i] == "1":
                continue

			# iterate through the solutions in range [i - maxJump, i - minJump]
			# and if any previous spot in range is reachable, then i is also reachable
            window_start = max(0, i - maxJump)
            window_end = i - minJump
            for j in range(window_start, window_end + 1):
                if dp[j]:
                    dp[i] = True
                    break
        
        return dp[-1]       
class Solution {
    public boolean canReach(String s, int minJump, int maxJump) {
        if(s.charAt(s.length() - 1) != '0')
            return false;
        
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        
        // This variable tells us till which index we have processed
        int maxReach = 0;
        
        while(!queue.isEmpty()){
            int idx = queue.remove();
            // If we reached the last index
            if(idx == s.length() - 1)
                return true;
            
            // start the loop from max of [current maximum (idx + minJump), maximum processed index (maxReach)]
            for(int j = Math.max(idx + minJump, maxReach); j <= Math.min(idx + maxJump, s.length() - 1); j++){
                if(s.charAt(j) == '0')
                    queue.add(j);
            }
            
            // since we have processed till idx + maxJump so update maxReach to next index
            maxReach = Math.min(idx + maxJump + 1, s.length() - 1);
        }
        
        return false;
    }
}
class Solution {
public:
    bool canReach(string s, int minJump, int maxJump) {
        int n = s.length();
        if(s[n-1]!='0')
            return false;
        
        int i = 0;
        queue<int> q;
        q.push(0);
        int curr_max = 0;
        
        while(!q.empty()){
            i = q.front();
            q.pop();
            if(i == n-1)
                return true;
            
            for(int j = max(i + minJump, curr_max); j <= min(i + maxJump, n - 1); j++){
                if(s[j] == '0')   q.push(j);
            }   
            curr_max = min(i+maxJump+1, n);
        }
        return false;
    }
};
var canReach = function(s, minJump, maxJump) {
    const validIdxs = [0];
    for (let i = 0; i < s.length; i++) {
        // skip if character is a 1 or if all the 
        // valid indicies are too close
        if (s[i] === '1' || i - validIdxs[0] < minJump) {
            continue;
        }
        
        // remove all the indexes that are too far
        while (validIdxs.length && i - validIdxs[0] > maxJump) {
            validIdxs.shift();
        }
        if (validIdxs.length === 0) {
            return false;
        }
        
        validIdxs.push(i);
        
        // if we are at the last index
        // return if we have an index within range
        if (i === s.length - 1) {
            return i - validIdxs[0] >= minJump;
        }
    }
    // if the last character is a 1 we must return False
    return false;
};
Jump Game VII