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);

}

Read full article from Count distinct occurrences as a subsequence - GeeksforGeeks