Let's Jump to Reach the Destination ✅✅ | Sliding Window 🪟
Intuition\nMy initial thought was to explore all possible jump paths from the starting index to the end of the string s. Given that you can jump between minJump
# Intuition\nMy initial thought was to explore all possible jump paths from the starting index to the end of the string `s`. Given that you can jump between `minJump` and `maxJump` from any index, a recursive approach seemed intuitive. However, this might lead to overlapping subproblems, hence using memoization was an initial idea to avoid recomputation. However, the recursive approach can still be inefficient due to its time complexity.\n\n# Approach\nThe more efficient approach involves dynamic programming with a sliding window mechanism:\n1. **DP Array**: We use a `dp` array where `dp[i]` is `true` if we can reach the `i-th` index starting from the beginning.\n2. **Sliding Window**: Instead of checking every possible jump for each index, we maintain a `reachable` sum that indicates how many positions within the sliding window `[i - maxJump, i - minJump]` are reachable. \n3. **Iterate**: As we iterate through the string, we update `reachable` and set `dp[i]` accordingly.\n4. **Return**: Finally, the value of `dp[n-1]` will tell us whether it\'s possible to reach the end of the string.\n\n# Complexity\n- **Time complexity**: $$O(n)$$, where `n` is the length of the string `s`. Each index is processed only once, making the solution linear in time.\n- **Space complexity**: $$O(n)$$, for the `dp` array which stores the reachability of each index.\n\n# Code\n```cpp []\nclass Solution {\n    // Recursion + Memoization Solution --> Gives TLE\n    //bool jumping(string &s, int minJump, int maxJump, int ind, vector<int> &dp){\n    //    int n = s.length();\n    //    if(ind>=n-1) return true;\n    //    if(s[ind]==\'1\') return dp[ind] = false;\n    //    if(dp[ind] != -1) return dp[ind];\n    //    for(int j = min(ind+maxJump, n-1); j>=(ind+minJump); j--){\n    //        if(jumping(s, minJump, maxJump, j, dp)) return dp[ind] = true;\n    //    }\n    //    return dp[ind] = false;\n    //}\npublic:\n    bool canReach(string s, int minJump, int maxJump) {\n        int n = s.length();\n        if(s[n-1]==\'1\') return false;\n        vector<bool> dp(n, false);\n        dp[0] = true;\n        int reachable = 0;\n        \n        for (int i = 1; i < n; i++) {\n            if (i >= minJump) reachable += dp[i - minJump];\n            if (i > maxJump) reachable -= dp[i - maxJump - 1];\n            \n            if (reachable > 0 && s[i] == \'0\') {\n                dp[i] = true;\n            }\n        }\n        \n        return dp[n - 1];\n    }\n};\n```
['Sliding Window', 'C++']