Java program to count common sub sequence in two strings

February 18, 2022

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 program
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)); 
  }
}

Output

Commonn sub sequence : 11