String DP Help

Please help me in this problem :
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