# Java program to count common sub sequence in two strings

## Count common sub sequence in two strings

In this article we are going to make a java program to count common sub sequence in two strings . We have given two strings, let’s say strings str1 and str2 containing characters and the task is to calculate the  common sub sequence in two strings . A sub sequence is a sequence that can be derived from another sequence by deleting some elements. Example : Input : str1 = “ajblqcpdz”, str2 = “aefcnbtdi”
Output : 11 ## Algorithm

•  Take two string and call CommomSubsequencesCount() method by passing both the string as a parameter of method .
• After that inside CommomSubsequencesCount() count the length of both the string and store it in the variable n2 , n2
• After that create 2-D array  int dp[][] = new int [n1+1][n2+1];
• Now run the for loop start from i=0 to i<=n1 , Inside this take j for loop start from j=0 to j<=n2
• Take another for loop next to the outer for loop start from i=0 to i<=n1 ,
• Inside that take another j for loop get the one by one character
• Check if ch1==ch2 then write dp[i][j] = 1 + dp[i][j – 1] + dp[i – 1][j]; else dp[i][j] = dp[i][j – 1] + dp[i – 1][j] – dp[i – 1][j – 1];

## Code in Java

```public class CountCommonSubSequenceInTwoStrings {

static int CommomSubsequencesCount(String s, String t) {
int n1 = s.length();
int n2 = t.length();
int dp[][] = new int [n1+1][n2+1];
char ch1,ch2 ;

for (int i = 0; i <= n1; i++) {
for (int j = 0; j <= n2; j++) {
dp[i][j] = 0;
}
}

for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++) {
ch1 = s.charAt(i - 1);
ch2 = t.charAt(j - 1);

if (ch1 == ch2)
dp[i][j] = 1 + dp[i][j - 1] + dp[i - 1][j];
else
dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1];
}
}

return dp[n1][n2];
}
public static void main (String args[]){
String s = "ajblqcpdz";
String t = "aefcnbtdi";
System.out.println("Common sub sequence : "+CommomSubsequencesCount(s, t));
}
}
This code is contributed by Shubham Nigam (Prepinsta Placement Cell Student)
```

## Output

`Commonn sub sequence : 11`