How can i solve this question by BitMasking?

#1

how can i solve this question by BitMasking??

#2

hey,
Actually this problem is Based On Dynamic Programing.
Optimize your solution .
Make 1 recursive call find all unique SubSequnce
HashMap use as Dp Array

The idea of this question is that for a certain string with distinct characters, you can have 2^n subsequences.

And subsequences will double itself for each additional character. for example for b there will be 2 subs, for ab there will be 4, for abc there will be 8.

Now if the characters are not distinct say “aba” your answer will be 2 * n - the subsequences of a. As A is repeated here.

Now you can use a hashmap as caching.

mod 10^9 + 7 is used, when your answer is coming out of the range. So it will prevent integer overflow.

#3

@aa1 i am using the recursion + set property to solve this question but getting some test case fails


brute forces i not able to get the overlapping subproblems

#4

but this problem in BitMasking section and i have not done DP yet.