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

java program to count common sub sequence in two string

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