Count distinct occurrences as a subsequence | Java program to count number of times S appears as a subsequence in T ; T can 't appear as a subsequence in S ; mat [ i ] [ j ] stores the count of occurrences of T ( 1. . i ) in S ( 1. . j ) . ; Initializing first column with all 0 s . An emptystring can 't have  another string as suhsequence ; Initializing first row with all 1 s . An empty string is subsequence of all . ; Fill mat [ ] [ ] in bottom up manner ; If last characters don 't match,  then value is same as the value  without last character in S. ; Else value is obtained considering two cases . a ) All substrings without last character in S b ) All substrings without last characters in both . ; uncomment this to print matrix mat for ( int i = 1 ; i <= m ; i ++ , cout << endl ) for ( int j = 1 ; j <= n ; j ++ ) System . out . println ( mat [ i ] [ j ] + " ▁ " ) ; ; Driver code to check above method
import java . io . * ; class GFG { static int findSubsequenceCount ( String S , String T ) { int m = T . length ( ) ; int n = S . length ( ) ; if ( m > n ) return 0 ; int mat [ ] [ ] = new int [ m + 1 ] [ n + 1 ] ; for ( int i = 1 ; i <= m ; i ++ ) mat [ i ] [ 0 ] = 0 ; for ( int j = 0 ; j <= n ; j ++ ) mat [ 0 ] [ j ] = 1 ; for ( int i = 1 ; i <= m ; i ++ ) { for ( int j = 1 ; j <= n ; j ++ ) { if ( T . charAt ( i - 1 ) != S . charAt ( j - 1 ) ) mat [ i ] [ j ] = mat [ i ] [ j - 1 ] ; else mat [ i ] [ j ] = mat [ i ] [ j - 1 ] + mat [ i - 1 ] [ j - 1 ] ; } } return mat [ m ] [ n ] ; } public static void main ( String [ ] args ) { String T = " ge " ; String S = " geeksforgeeks " ; System . out . println ( findSubsequenceCount ( S , T ) ) ; } }