# Java program to count common sub sequence in two strings

## Counting Common Subsequence in two Strings

In this article we are going to make a java program to Count Common Subsequence 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 (Count Common Subsequence in two Strings)

```//Count Common Subsequence in two Strings Java programpublic 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));
}
}
```

## Output

`Commonn sub sequence : 11`