Count subsequences by dp

#1

https://hack.codingblocks.com/contests/c/512/1097

IN THIS I DONT UNDERSTAND THE CORRECTNESS OF LOGIC GIVEN ON GEEKS FOR GEEKS SITE

how by removing the count of till last occurance of some character which was repeated got us the right answer

e.g in this string abca;
the following will be the subsequences generated am just generating so as to analyse the correctness of logic
_ first i have NULL string this is index 0 , dp[0]=1;
‘a’ _ index 1 dp[1]=2*dp[1-1]=2
‘ab’ ‘b’ ‘a’ _
‘abc’ ‘bc’ ‘ac’ ‘c’ ‘ab’ ‘b’ ‘a’ _
now adding a and seeing the repetitions
‘abca’ ‘bca’ ‘aca’ ‘ca’ ‘aba’ ‘ba’ ‘aa’ ‘a’ ‘abc’ ‘bc’ ‘ac’ ‘c’ ‘ab’ ‘b’ ‘a’ _
1…2…3… 4…5…6…7…8…9…10…11…12…13…14…15 …16

repetitions
2 and 9
4 and 11
8 and 15
6 and 13

TOTAL 4
so i need to subtract 4 from the formula dp[i]=2*dp[i-1]; to reduce repetitions and note that 4!=the subsequences of last index i.e dp[1] which is equal to 2

SO THATS WHY I AM FINDING TROUBLE UNDERSTANDING THIS BCOZ I AM ABLE TO FIND A CASES WHERE THIS WILL GET ME WRONG ANS

#2

Hey Jai, this approach is correct and you can refer this article for the proof of its correctness to visualize how it is working. As you are saying it will not work for some test case, can you share that test case for which it will give the wring output.

#3

e.g in this string abca;
the following will be the subsequences generated am just generating so as to analyse the correctness of logic
_ first i have NULL string this is index 0 , dp[0]=1;

‘a’ _ dp[1]=2*dp[1-1]=2 (THIS IS THE FIRST OCCURANCE OF ‘a’ so it becomes the last index of ‘a’
‘ab’ ‘b’ ‘a’ _
‘abc’ ‘bc’ ‘ac’ ‘c’ ‘ab’ ‘b’ ‘a’ _
now adding a and seeing the repetitions
‘abca’ ‘bca’ ‘aca’ ‘ca’ ‘aba’ ‘ba’ ‘aa’ ‘a’ ‘abc’ ‘bc’ ‘ac’ ‘c’ ‘ab’ ‘b’ ‘a’ _
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

repetitions
2 and 9
4 and 11
8 and 15
6 and 13

TOTAL 4
so i need to subtract 4 from the formula dp[i]=2dp[i-1]; i.e to reduce repetitions (dp[i]=2dp[i-1]-4 for this particular case) and note that 4 is not equal to the number of subsequences of last index i.e dp[1] which is equal to 2

#4

i found my mistake by writing this elaborate doubt :sweat_smile:

#5

Great :+1: debugging the code always helps :slight_smile: