[Java] DP optimized using Deque : O(N)
Intuition\n Describe your first thoughts on how to solve this problem. \nTo reach i, we must know whether we can reach any "0" that falls between [i - maxJump, 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo reach i, we must know whether we can reach any "0" that falls between [i - maxJump, i - minJump]. So finding if the "0" in that range is reachable become the subproblem to solve first if we want to solve for i. Thus it\'s a dynamic programmming problem.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nHowever, for each dp[i], if we need to itereate all [i-maxJump, i-minJump] looks not efficient O(N*window). \nWe can improve by maintain a window of indices of "0" in that window. And we shift the window together.\n- right pointer is the one entering the window, so we check dp[r] and add it to a deque if it\'s true\n- left pointer is the one leaving the window, so we check top of the deque if that\'s the index leaving, if  so we remove it from the deque\n\nthis works because we are adding the indices from left to right and we only check if the size of queue is 0. If not 0, that means in that window we have a reachable "0", which makes the current position reachable, set dp[i]=true. \nBy the time our right pointer reach a position, that position already calculated since i > r, so we can check dp[r] to decide if we can include it in the queue.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(N)\n\n# Code\n## DP - O (N*winSize)\n```\nclass Solution {\n    public boolean canReach(String s, int minJump, int maxJump) {\n        int n = s.length();\n        if (s.charAt(n-1) != \'0\') {\n            return false;\n        }\n\n        boolean[] dp = new boolean[n];\n        dp[0] = true;\n\n        for (int i = minJump; i < n; ++i) {\n            if (s.charAt(i) == \'0\') {\n                int start = i - maxJump >= 0 ? i - maxJump : 0;\n                for (int j = start; j <= i - minJump; ++j) {\n                    if (dp[j]) {\n                        dp[i] = true;\n                        break;\n                    }\n                }\n            }\n        }\n\n        return dp[n-1];\n    }\n}\n```\n## DP + Deque - O(N)\n```\nclass Solution {\n    public boolean canReach(String s, int minJump, int maxJump) {\n        int n = s.length();\n        int l = 0, r = 0;\n        int winSize = maxJump - minJump + 1;\n\n        boolean[] dp = new boolean[n];\n\n        // to keep track of reachable "0" in the previous window\n        LinkedList<Integer> queue = new LinkedList<>();\n\n        dp[0] = true;\n        for (int i = minJump; i < n; ++i) {\n            if (dp[r]) {\n                queue.addLast(r);\n            }\n\n            if (s.charAt(i) == \'0\' && !queue.isEmpty()) {\n                // if there is any reachabke "0" in previous window, current is reachable\n                dp[i] = true;\n            }\n\n            if (r - l == winSize - 1) {\n                if (!queue.isEmpty() && queue.getFirst() == l) {\n                    queue.removeFirst();\n                }\n                ++l;\n            }\n            ++r;\n        }\n\n        return dp[n-1];\n    }\n}\n```
['Linked List', 'Dynamic Programming', 'Sliding Window', 'Java']