- binary-string, Dynamic Programming, Greedy, Mathematical, Strings

Check if end of given Binary string can be reached by choosing jump value in between given range

Given two positive integers L and R and a binary string S of size N, the task is to check if the end of the string is reached from the index 0 by a series of jumps of indices, say i such that S[i] is 0 jumps are allowed in the range [L, R]. If it is possible to reach, then print Yes. Otherwise, print No.Examples:Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.Input: S = “011010”, L = 2, R = 3Output: YesExplanation:Following are the series of moves having characters at that indices as 0:S[0](= 0) -> S[3](= 0) -> S[5](= 0) and S[5] is the end of the string S.Therefore, print Yes.Input: S = “01101110”, L = 2, R = 3Output: NoApproach: The above problem can be solved with the help of Dynamic Programming, the idea is to maintain 1D array, say dp[] where dp[i] will store the possibility of reaching the ith position and update each index accordingly. Below are the steps:Initialize an array, dp[] such that dp[i] stores whether any index i can be reached from index 0 or not. Update the value of dp[0] as 1 as it is the current standing index.Initialize a variable, pre as 0 that stores the number of indices from which the current index is reachable.Iterate over the range [1, N) and update the value of pre variable as follows:If the value of (i >= minJump), then increment the value of pre by dp[i – minJump].If the value of (i > maxJump), then decrement the value of pre by dp[i – maxJump – 1].If the value of pre is positive, then there is at least 1 index from which the current index is reachable. Therefore, update the value of dp[i] = 1, if the value of S[i] = 0.After completing the above steps, if the value of dp[N – 1] is positive, then print Yes. Otherwise, print No.Below is the implementation of the above approach:C++#include using namespace std;  bool canReach(string s, int L, int R){        vector dp(s.length());          dp[0] = 1;              int pre = 0;          for (int i = 1; i < s.length(); i++) {                          if (i >= L) {            pre += dp[i – L];        }                          if (i > R) {            pre -= dp[i – R – 1];        }          dp[i] = (pre > 0) and (s[i] == ‘0’);    }          return dp[s.length() – 1];}  int main(){    string S = “01101110”;    int L = 2, R = 3;      cout