Intuitive Solution using suffix-sum array O(n) solution
The base case: if the last character of the string is not \'1\', there is no way to reach there.\n\nThe intuitive solution is to use a BFS. We try to reach ever
The base case: if the last character of the string is not \'1\', there is no way to reach there.\n\nThe intuitive solution is to use a BFS. We try to reach every valid & possible index starting from the 0th index. By valid & possible index I mean, every index (j) which is reachable using given jump range from the current index (i) and has a value \'0\' at s[j].  If it is possible to reach the last index, we can return true, else false.\n\n```\nbool canReach(string s, int minJump, int maxJump) {\n        int n = s.size();\n        if(s[n-1] != \'0\') return false;\n        queue<int> q;\n        vector<bool> vis(n, false);\n        q.push(0);\n        vis[0] = true;\n        while(!q.empty()){\n            int curr_index = q.front();\n            q.pop();\n            if(curr_index == n-1) return true;\n            for(int j = curr_index + minJump; j <= min(curr_index + maxJump, n-1); j++){\n                if(s[j] == \'0\' && !vis[j]){\n                    vis[j] = true;\n                    q.push(j);\n                }\n            }\n        }\n        return false;\n    }\n```\n\nSo, in this approach, we try to see what all indices we can reach given it is possible to reach the current index. The time complexity of this approach is O(N^2). \n\nHow do we know that if we start from a particular index, we can reach the last index? \nWe need to check two conditions for this, if both are satisfied, we can reach the last index.\n1. The value at current index is \'0\'. If it is \'1\', it is not a valid index and we can;t reach last index from here.\n2. Let the current index be curr_index. So, if there is any index in the range [curr_index + minJump, curr_index + maxJump] from where we can reach the last index, we can reach the last index from this curr_index also.\n\nNow the base case. If the last index is having value \'1\', there is no way to reach this last index. It is possible to reach the last index from the last index. We can iterate from (n-2)th index to 0th index and go on checking if its possible to reach the last index fron this particular index. The most important thing is how to efficently know whether there is any index in the range [curr_index + minJump, curr_index + maxJump] from where we can reach the last index. We can use suffix array for this. The suffic_array[i] contains the count of the number of such indices from ith index till the (n-1)th index from where we can reach the last index. Hence, for any current index, we just need to check if there is atleast 1 such index in the range [curr_index + minJump, curr_index + maxJump]. The count of indices from where it is possible to reach last index in the range [curr_index + minJump, curr_index + maxJump] is given by suffix_array[curr_index + minJump] - suffix_array[curr_index + maxJump  + 1]. \n\n```\nbool canReach(string s, int minJump, int maxJump) {\n        int n = s.size();\n        if(s[n-1] == \'1\') return false;\n        vector<int> suffix(n, 0);\n        vector<bool> can_visit(n, false);\n        suffix[n-1] = 1;\n        can_visit[n-1] = true;\n        for(int i=n-2;i>=0;i--){\n            if(s[i] == \'1\'){\n                suffix[i] = suffix[i+1];\n            }\n            else{\n                int cnt = 0;\n                if(i+minJump < n) cnt = suffix[i+minJump];\n                if(i+maxJump+1 < n) cnt -= suffix[i+maxJump+1];\n                if(cnt){\n                    suffix[i] = suffix[i+1] + 1;\n                    can_visit[i] = true;\n                }\n                else{\n                    suffix[i] = suffix[i+1];\n                }\n            }\n        }\n        return can_visit[0];\n    }\n```\n\nTime Complexity : O(N)\nSpace Complexity : O(N)
['C']