Count Subsequence Problem Using Bitmasking

#1

How can I solve this question using bitmasking? I am aware of the recursive and dp solution but please tell me about the bitmasking approach

#2

@ap8730390 Bro, first I want to see your approach, so first post your submission here, because it seems you haven’t submitted it yet, so first post the submission, with your approach.

Or either tell me the recursion and dp approach to it. And by your approach I mean your code, and your intuition for the approach, because this problem is a good dp problem again a combinatorial optimization problem. Think it with dp, dp is the best approach to this problem.

There should be a reason to apply a specific paradigm. Rather than going for bitmasking go for dp, because you have to find out count of distinct subs. And while finding count, don’t generate all the subsequences. In dp don’t generate side effect outputs. Here we don’t have to generate all possible candidates of outputs so go with dp rather than bitmasking

#3

This was my approach but I don’t know how to use 10^7 in problems like these.Please help

#4

@ap8730390 Bro where is your recursive and memoized approach, instead of approaching bottom up solutions on the net first come up with a recursive approach, then only you will learn dp.
Lemme know if you aren’t able to come up with the approach.

#5

Okay! Thanks @Kartik, I’ll definitely try memoization approach. But can you tell me a bit where we have to use mod=10000007

#6

*1000000007. Sorry :frowning:

#7

@ap8730390 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.

I am posting my memoized code here bro, my advice is don’t search the solutions on net. Just try because on net you will get iterative solutions and they are not intuitive to the beginners at all.

public static int distinSub(String S, HashMap<Character, Integer> subs) {
    if(S.length() == 0) {
        return 1;
    }
    char cc = S.charAt(0);
   //Bottom Up manner.
    int count = distinSub(S.substring(1), subs);

   /* Store the character and corresponding count in the hashmap,
      if the key is encountered again that's mean the character is repeatitive so subtract its  
      subsequences from the total count i.e 2*n - the subs due to that character else put the 
      character and corresponding count into hashmap.
    */
    if(subs.containsKey(cc)) {
        int val = subs.get(cc);
        int ans = (2 * count % 1000000007 - val + 1000000007) % 1000000007;
        subs.put(cc, count);
        return ans;
    } else {
        int ans = (2 * count) % 1000000007;
        subs.put(cc, count);
        return ans;
    }
}