Spoj (DSUBSEQ) – Distinct Subsequences

http://www.spoj.com/problems/DSUBSEQ/

Consider the string “ABCD”

Let dp[i] = { number of subsequences possible from string[1…i]}

Note : we are considering 1 based string array

what are all the possible subsequences

dp[0] = 1   { }

dp[1]= 2   { } ,A

dp[2] = 4  { } ,A ,B ,AB

dp[3] = 8  { } ,A ,B ,AB ,C ,AC,BC,ABC

dp[4] = 16 { } ,A ,B ,AB ,C ,AC,BC,ABC,D,AD,BD,ABD,CD,ACD,BCD ,ABCD

So do we get some kind of pattern ?

yes!

dp[i]= dp[i-1]*2

(sum of all subseq till string[1…i-1] + sum of subseq till string[1…i-1] concatenated with character string[i])

There one more case we have to consider

if we have duplicate characters in the string then our subsequence will also be duplicated

To prevent that have a last[ ] array to store position of string[i] which occured before

last[string[i]]= last occurence of string[i]

substract subsequence count occured till position (last[string[i]]-1) since it is repeated again

so the correct recursion rule is

dp[i]=dp[i-1]*2;

if(last[string[i]]>0)

dp[i]=(dp[i]-dp[last[string[i]]-1]);