TLE reported in "Count Subsequences" problem of BitMasking

#1

THIS CODE HAS PASSED ONLY FIRST TEST CASE. REST ALL ARE GIVING TLE.

import java.util.*;
public class SubSequences
{
static HashMap<String,Boolean> map;
public static void printSS(String str)
{
int n=str.length();
int len=(1<<n);
for(int i=0;i<len;i++)
Sub(str,i,"");
}
public static void Sub(String str,int i,String temp)
{
int n=str.length();
int j=0;
while(i>0)
{
int lastBit=1&i;
if(lastBit==1)
{
temp=temp+str.charAt(j);
}
j++;
i=i>>1;
}
if(!map.containsKey(temp))
map.put(temp,true);
}
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int T=sc.nextInt();
for(int i=0;i<T;i++)
{
map=new HashMap<>();
String str=sc.next();
printSS(str);
System.out.println(map.size());
}
}
}

#2

@vinay86048
you have to use Dynamic programming here otherwise you will get TLE
Consider the string S=“ABCB”

Let DP[i+1] = No. of distinct subsequences possible from S[0…i]

where DP[0] = 1, for empty subsequence { }

So, for the string “ABCDEFG”

For i=0;

Possible Subsequences: { },A

DP[1] = 2;

For i=1:

Possible Subsequences: { },A,B,AB

DP[2] = 4

for i=2:

Possible Subsequences: { },A,B,AB,C,AC,BC,ABC

DP[3] = 8

As we can observe,

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

But till now, all characters were distinct.

Consider the next chracter ‘B’(Getting repeated),

Possible Subsequences:

{ },A,B,AB,C,AC,BC,ABC,B,AB,BB,ABB,CB,ACB,BCB,ABCB

DP[4] = 16

But here as we can see, (B,AB) are repeating (hence the subsequences are not distinct), Which we had obtained earlier by appending B at the end to ({ },A).

Hence the No. of repeating subsequences = DP[1] in this case.

Where, 1 is nothing but the previous occurence of the characer B. And we need to subtract the no. of repeating subsequences to get the result.

In this case,

DP[4] = 16 - 2 = 14

Hence DP[i] = DP[i-1]*2 - DP[Immediate previous occurence of character S[i-1]], if S[i-1] has occurred before.

Final Algo. obtained:

DP[0] = 1;

For i=0 to length(S)-1:

DP[i+1] = DP[i]*2;

if(previous[S[i]]>=0)

DP[i+1] = DP[i+1] - DP[previous[S[i]]];

previous[S[i]] = i;

Expected Output: DP[length(S)]

Note:

Previous[i] = Index of prev. occurence of i. If there is no previous occurence of i, then I have initialized it to some negative value.

#3

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.