# 4ms java solution, O(S + T) on average, O(S * T) worst case, O(T) space

• Sequentially scan every char c in S. During the process, maintain an int array Prefix with length T, in which the i th element hold the number of founded prefix T[0 ~ i-1]. How do we update array Prefix? For each c you scan from S, find the index(or indices) of c in T which we write down as index(c), Simply update Prefix[ index(c) ] by adding Prefix[ index(c) - 1 ]. Explanation: Say if you have S "rabbbit", T"rabit" and you are currently scanning the second 'b' in S. You find that 'b' the number of prefix 'ra' is 1 and you simply add the number of founded prefix 'rab' by 1. which is 2 now.

``````Map<Character, List<Integer>> map;
public int numDistinct(String s, String t)
{
int[] sumBuffer = new int[t.length()];
map = new HashMap<Character, List<Integer>>();
for(int i = 0; i < t.length(); i++)
{
char c = t.charAt(i);
List<Integer> indices = map.get(c);
if(indices == null)
{
indices = new ArrayList<Integer>();
map.put(c, indices);
}
else
{
}
}
for(int i = 0; i < s.length(); i++)
{
char c = s.charAt(i);
List<Integer> indices = map.get(c);
if(indices != null)
{
for(int j = indices.size()-1; j >=0; j--)
{
int index = indices.get(j);
if(index == 0)
{
sumBuffer[0]++;
}
else
{
sumBuffer[index] += sumBuffer[index-1];
}
}
}
}
return sumBuffer[t.length()-1];
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.