example1:

S = "rabbbit", T = "rabbit"

we have "ArrayList[] tIndex=new ArrayList[52]" to record something,

tIndex[0]=1,tIndex[1]=2,3,tIndex[8]=4

because in String T,a appear at 1,b appear at 2,3,i appear at 4 and so on.

results[0] means how many "r" we have by far;

results[1] means how many "ra" we have by far;

results[2] means how many "rab" we have by far;

....

results[5] means how many "rabbit" we have by far;that is what we need

at first all results is 0.

now we look at String S from start to end and update the results.

"for(int i=0;i<s.length();i++)"

now i=0,we is at 'r' in S,so result[0]=1,because we have a 'r' by far.

and now i=1,we is at 'a' in S,so result[1]=1,because we already have a 'r' before and 'r'+'a'="ra",so we now have a "ra".

now i=2,we is at 'b' in S,so result[2]=1.

now i=3,we is at 'b'(the second one) in S,so result[2]=1+1, result[3]=1

because we already have a "ra",so we have a new "rab",and add the old "rab",now we have two "rab",

and with the new "b" ,we can form a "rabb".

i=4,we is at 'b'(the third one) in S,,we can form some new "rab" and "rabb" so result[2]=2+1.result[3]=1+2.

i=5,we is at 'i' in S,,we can form some new "rabbi" so result[4]=3.

i=6,we is at 't' in S,,we can form some new "rabbit" so result[5]=3.

class Solution {

public int numDistinct(String s, String t) {

if(t.length()==0)

return 0;

```
ArrayList[] tIndex=new ArrayList[52];
for(int i=0;i<t.length();i++){
int index=0;
if(t.charAt(i)>='a')
index=t.charAt(i)-'a';
else
index=t.charAt(i)-'A'+26;
if(tIndex[index]==null)
tIndex[index]=new ArrayList();
tIndex[index].add(i);
}
int[] results=new int[t.length()];
for(int i=0;i<s.length();i++){
int index=0;
if(s.charAt(i)>='a')
index=s.charAt(i)-'a';
else
index=s.charAt(i)-'A'+26;
if(tIndex[index]==null)
continue;
for(int j=tIndex[index].size()-1;j>=0;j--){
int k=(Integer) tIndex[index].get(j);
if(k==0)
results[k]++;
else
results[k]+=results[k-1];
}
}
return results[t.length()-1];
}
```

}