## Wednesday, October 5, 2016

### Count distinct occurrences as a subsequence - GeeksforGeeks

LeetCode 115 - Distinct Subsequences
Count distinct occurrences as a subsequence - GeeksforGeeks
Given a two strings S and T, find count of distinct occurrences of T in S as a subsequence.
```Input  : S = geeksforgeeks, T = ge
Output : 6
T appears in S as below three subsequences.
[ge], [     ge], [g e], [g    e] [g     e]
and [     g e]      ```

```// Returns count of subsequences of S that match T
// m is length of T and n is length of S
subsequenceCount(S, T, n, m)

// An empty string is subsequence of all.
1) If length of T is 0, return 1.

// Else no string can be a sequence of empty S.
2) Else if S is empty, return 0.

3) Else if last characters of S and T don't match,
remove last character of S and recur for remaining
return subsequenceCount(S, T, n-1, m)

4) Else (Last characters match), the result is sum
of two counts.

// Remove last character of S and recur.
a) subsequenceCount(S, T, n-1, m) +

// Remove last characters of S and T, and recur.
b) subsequenceCount(S, T, n-1, m-1)        ```

Since there are overlapping subproblems in above recurrence result, we can apply dynamic programming approach to solve above problem. We create a 2D array mat[m+1][n+1] where m is length of string T and n is length of string S. mat[i][j] denotes the number of distinct subsequence of substring S(1..i) and substring T(1..j) so mat[m][n] contains our solution.
Time Complexity : O(m*n)
Auxiliary Space : O(m*n)
Since mat[i][j] accesses elements of current row and previous row only, we can optimize auxiliary space just by using two rows only reducing space from m*n to 2*n.

`int` `findSubsequenceCount(string S, string T)`
`{`
`    ``int` `m = T.length(), n = S.length();`
`    ``// T can't appear as a subsequence in S`
`    ``if` `(m > n)`
`        ``return` `0;`
`    ``// mat[i][j] stores the count of occurrences of`
`    ``// T(1..i) in S(1..j).`
`    ``int` `mat[m + 1][n + 1];`
`    ``// Initializing first column with all 0s. An empty`
`    ``// string can't have another string as suhsequence`
`    ``for` `(``int` `i = 1; i <= m; i++)`
`        ``mat[i][0] = 0;`
`    ``// Initializing first row with all 1s. An empty`
`    ``// string is subsequence of all.`
`    ``for` `(``int` `j = 0; j <= n; j++)`
`        ``mat[0][j] = 1;`
`    ``// Fill mat[][] in bottom up manner`
`    ``for` `(``int` `i = 1; i <= m; i++)`
`    ``{`
`        ``for` `(``int` `j = 1; j <= n; j++)`
`        ``{`
`            ``// If last characters don't match, then value`
`            ``// is same as the value without last character`
`            ``// in S.`
`            ``if` `(T[i - 1] != S[j - 1])`
`                ``mat[i][j] = mat[i][j - 1];`
`            ``// Else value is obtained considering two cases.`
`            ``// a) All substrings without last character in S`
`            ``// b) All substrings without last characters in`
`            ``//    both.`
`            ``else`
`                ``mat[i][j] = mat[i][j - 1] + mat[i - 1][j - 1];`
`        ``}`
`    ``}`
`    ``/* uncomment this to print matrix mat`
`    ``for (int i = 1; i <= m; i++, cout << endl)`
`        ``for (int j = 1; j <= n; j++)`
`            ``cout << mat[i][j] << " ";  */`
`    ``return` `mat[m][n] ;`
`}`

http://www.geeksforgeeks.org/find-number-times-string-occurs-given-string/
`int` `count(string a, string b, ``int` `m, ``int` `n)`
`{`
`    ``// If both first and second string is empty,`
`    ``// or if second string is empty, return 1`
`    ``if` `((m == 0 && n == 0) || n == 0)`
`        ``return` `1;`

`    ``// If only first string is empty and second`
`    ``// string is not empty, return 0`
`    ``if` `(m == 0)`
`        ``return` `0;`

`    ``// If last characters are same`
`    ``// Recur for remaining strings by`
`    ``// 1. considering last characters of both strings`
`    ``// 2. ignoring last character of first string`
`    ``if` `(a[m - 1] == b[n - 1])`
`        ``return` `count(a, b, m - 1, n - 1) +`
`               ``count(a, b, m - 1, n);`
`    ``else`
`        ``// If last characters are different, ignore `
`        ``// last char of first string and recur for `
`        ``// remaining string`
`        ``return` `count(a, b, m - 1, n);`
`}`