Question:

How to find a count of distinct occurrences of an element using Java

Summary

To determine the number of subsequences of string s that match string t, we are putting a dynamic programming solution into practice here.

Solution

/*You are required to complete this method*/

class Solution

{

int subsequenceCount(String s, String t)

{

// Your code here

int m=t.length();

int n=s.length();

int dp[][]=new int[m+1][n+1];

int mod = 1000000007;

int ans=0;

for(int i=1;i<=m;i++)

dp[i][0]=0;

for(int i=0;i<=n;i++)

dp[0][i]=1;

for(int i=1;i<=m;i++)

{

Character cur = t.charAt(i-1);

int cnt=1;

for(int j=1;j<=n;j++)

{

if(s.charAt(j-1)==cur)

dp[i][j]=(dp[i][j-1]%mod+dp[i-1][j-1]%mod)%mod;

else dp[i][j]=dp[i][j-1]%mod;

}

return dp[m][n]%mod;

}

Explanation

The function int subsequenceCount(String s, String t) accepts two strings, s and t, as input and outputs an integer that indicates the number of subsequences of s that match t.
The lengths of the strings t and s are initialized for m and n, respectively, using int m = t.length() and int n = s.length().
To store the dynamic programming values, a 2D array dp of size (m + 1) x (n + 1) is initialized. int dp[][] = new int[m + 1][n + 1];.