Please help me in this problem : https://leetcode.com/discuss/interview-question/124943/dynamic-programming/125712

People have just given the codes, I want to implement it on my own. Please suggest some approach.

@everule1 @carre @ssjgz

the statement looks incomplete. What time complexity are you expecting? O(s*n) ?

If thatâ€™s the case use a simple dp where for each character of the string from left to write you add 1 to the left (or right) position for every non-empty position

Yeah O(s*n) should be fine but how to solve distinct part? Can you tell the states of your dp?

dp[i] is just the number of ways to finish in position i

- initiate dp[i]=0 for all i except i=start; dp[start]=1

- for each character c in s,
- if c=1: do from n-1 to 0: dp[i]=dp[i+1]+1 (only if dp[i+1]>0);
- else: do from 1 to n: dp[i] = dp[i-1]+1 (only if dp[i-1]>0)

the answer is dp[finish]

I think it can be done in \mathcal{O}( (s+n) * log\, n) using a segment tree or bit with range updates