Tle in all cases

#1

please tell a better approach and how to remove tle from this

#2

Hey @Akshita99
Your solution is a recursive solution and this is a Dynamic Programming question so if you haven’t studied it yet then leave this question otherwise let me know and I will explain you how to approach it.

#3

i have studied it but cant think of a dp solution

#4

Hey @Akshita99
Using Dynamic Programming

Let countSub(n) be count of subsequences of first n characters in input string. We can recursively write it as below. countSub(n) = 2*Count(n-1) - Repetition
If current character, i.e., str[n-1] of str has not appeared before, then Repetition = 0
Else: Repetition = Count( m ) Here m is index of previous occurrence of current character. We basically remove all counts ending with previous occurrence of current character.

How does this work?
If there are no repetitions, then count becomes double of count for n-1 because we get count(n-1) more subsequences by adding current character at the end of all subsequences possible with n-1 length.
If there repetitions, then we find count of all distinct subsequences ending with previous occurrence. This count can be obtained be recursively calling for index of previous occurrence.

Since above recurrence has overlapping subproblems, we can solve it using Dynamic Programming.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#6

https://ide.codingblocks.com/s/333553. please check the problem in the code

#7

hey @Akshita99 i have made some changes in your code and now it is passing all the test cases .


if you have any doubt please reply here .
Happy Learning !!

#8

here in last_occ[s[i-1]] why do we store i-1 and not i?

#9

dp[i]=(dp[i]-dp[last_occur[s[i-1]]]+mod)%mod; and why +mod is done here?

#10

dp[i]=(dp[i]-(dp[mp[s[i-1]]]-dp[mp[s[i-1]]-1]))%mod; shouldnt this line be used as we have to remove all ocurrences of that character when it appeared as last index and at dp[mp[s[i-1]]] we have all possible values till that character and at dp[mp[s[i-1]]-1] we have all values till its prev character so their difference will give no of subsequences ending with that character as last index

#11

https://ide.codingblocks.com/s/333553 see my code to better understand what i am trying to say

#12

@Akshita99 if you dry run the code for any small test case you will understand it in a better way .

#13

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.