DEFINITION
A string k is a subsequence of a string x if the letters of k appear in order
in x. i.e., "abc" is a subsequence of "azzzzbzzzzc". "abc" is also a
subsequence of "abc" and of "abcabc". However, "abc" is not a subsequence of
"acb", since the letters to not appear in order.
PROBLEM STATEMENT
Class name: Subsequences
Method name: numDistinct
Parameters: String, String
Returns: int
Method signature (make sure it is declared public):
int numDistinct(String tofind, String base);
Given two Strings, you must determine how many distinct ways the first String
can be expressed as a subsequence of the second String. For instance, given
parameters of "abc", "ababcde": "abc" can be constructed as the character at
index 0, index 1, and index 4; or the characters at index 0, index 3, and index
4; or characters at index 2, index 3, and index 4. This yields 3 distinct
solutions, thus, the method returns 3.
TopCoder will enforce the following restrictions:
* tofind will be between 1 and 12 characters, inclusive.
* base will be between 0 and 24 characters, inclusive.
* tofind and base will include only lowercase letters (a-z).
Example 1:
"abc","abcabc" returns 4
Example 2:
"abc","aaabbbcccaaabbbc" returns 54
Example 3:
"aaa","aaaaaaaaaaaa" returns 220