Count common subsequence in two strings

Try it on GfG Practice

Given two string S and T. The task is to count the number of the common subsequence in S and T.

Examples:

Input : S = "ajblqcpdz", T = "aefcnbtdi" 
Output : 11 
Common subsequences are : { "a", "b", "c", "d", "ab", "bd", "ad", "ac", "cd", "abd", "acd" }

Input : S = "a", T = "ab" 
Output : 1

To find the number of common subsequences in two string, say S and T, we use Dynamic Programming by defining a 2D array dp[][], where dp[i][j] is the number of common subsequences in the string S[0...i-1] and T[0....j-1]. 

Now, we can define dp[i][j] as = dp[i][j-1] + dp[i-1][j] + 1, when S[i-1] is equal to T[j-1] 
This is because when S[i-1] == S[j-1], using the above fact all the previous common sub-sequences are doubled as they get appended by one more character. Both dp[i][j-1] and dp[i-1][j] contain dp[i-1][j-1] and hence it gets added two times in our recurrence which takes care of doubling of count of all previous common sub-sequences. Addition of 1 in recurrence is for the latest character match : common sub-sequence made up of s1[i-1] and s2[j-1]  = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1], when S[i-1] is not equal to T[j-1] 
Here we subtract dp[i-1][j-1] once because it is present in both dp[i][j - 1] and dp[i - 1][j] and gets added twice.

Implementation:

// C++ program to count common subsequence in two strings #include <bits/stdc++.h> using namespace std; // return the number of common subsequence in // two strings int CommonSubsequencesCount(string s, string t) {  int n1 = s.length();  int n2 = t.length();  int dp[n1+1][n2+1];  for (int i = 0; i <= n1; i++) {  for (int j = 0; j <= n2; j++) {  dp[i][j] = 0;  }  }  // for each character of S  for (int i = 1; i <= n1; i++) {  // for each character in T  for (int j = 1; j <= n2; j++) {  // if character are same in both   // the string  if (s[i - 1] == t[j - 1])   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]; } // Driver Program int main() {  string s = "ajblqcpdz";  string t = "aefcnbtdi";  cout << CommonSubsequencesCount(s, t) << endl;  return 0; } 

// Java program to count common subsequence in two strings public class GFG {    // return the number of common subsequence in   // two strings   static int CommonSubsequencesCount(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 each character of S   for (int i = 1; i <= n1; i++) {     // for each character in T   for (int j = 1; j <= n2; j++) {     ch1 = s.charAt(i - 1);  ch2 = t.charAt(j - 1);    // if character are same in both   // the string   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];   }   // Driver code   public static void main (String args[]){    String s = "ajblqcpdz";   String t = "aefcnbtdi";     System.out.println(CommonSubsequencesCount(s, t));     } // This code is contributed by ANKITRAI1 } 

// C# program to count common  // subsequence in two strings using System; class GFG  { // return the number of common  // subsequence in two strings  static int CommonSubsequencesCount(string s,   string t)  {   int n1 = s.Length;   int n2 = t.Length;   int[,] dp = new int [n1 + 1, n2 + 1];     for (int i = 0; i <= n1; i++)   {   for (int j = 0; j <= n2; j++)   {   dp[i, j] = 0;   }   }     // for each character of S   for (int i = 1; i <= n1; i++)  {     // for each character in T   for (int j = 1; j <= n2; j++)  {    // if character are same in   // both the string   if (s[i - 1] == t[j - 1])   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];  }  // Driver code  public static void Main () {  string s = "ajblqcpdz";   string t = "aefcnbtdi";     Console.Write(CommonSubsequencesCount(s, t));  } } // This code is contributed // by ChitraNayal 

<script> // Javascript program to count common subsequence in two strings // return the number of common subsequence in // two strings function CommonSubsequencesCount(s, t) {  var n1 = s.length;  var n2 = t.length;  var dp = Array.from(Array(n1+1), ()=> Array(n2+1));  for (var i = 0; i <= n1; i++) {  for (var j = 0; j <= n2; j++) {  dp[i][j] = 0;  }  }  // for each character of S  for (var i = 1; i <= n1; i++) {  // for each character in T  for (var j = 1; j <= n2; j++) {  // if character are same in both   // the string  if (s[i - 1] == t[j - 1])   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]; } // Driver Program var s = "ajblqcpdz"; var t = "aefcnbtdi"; document.write( CommonSubsequencesCount(s, t)); </script> 

<?php // PHP program to count common subsequence // in two strings // return the number of common subsequence // in two strings function CommonSubsequencesCount($s, $t) { $n1 = strlen($s); $n2 = strlen($t); $dp = array(); for ($i = 0; $i <= $n1; $i++) { for ($j = 0; $j <= $n2; $j++) { $dp[$i][$j] = 0; } } // for each character of S for ($i = 1; $i <= $n1; $i++) { // for each character in T for ($j = 1; $j <= $n2; $j++) { // if character are same in both  // the string if ($s[$i - 1] == $t[$j - 1]) $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]; } // Driver Code $s = "ajblqcpdz"; $t = "aefcnbtdi"; echo CommonSubsequencesCount($s, $t) ."\n"; // This code is contributed  // by Akanksha Rai ?> 

# Python3 program to count common # subsequence in two strings # return the number of common subsequence  # in two strings def CommonSubsequencesCount(s, t): n1 = len(s) n2 = len(t) dp = [[0 for i in range(n2 + 1)] for i in range(n1 + 1)] # for each character of S for i in range(1, n1 + 1): # for each character in T for j in range(1, n2 + 1): # if character are same in both  # the string if (s[i - 1] == t[j - 1]): 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] # Driver Code s = "ajblqcpdz" t = "aefcnbtdi" print(CommonSubsequencesCount(s, t)) # This code is contributed by Mohit Kumar 

11

Complexity Analysis:

• Time Complexity : O(n1 * n2) 
• Auxiliary Space : O(n1 * n2)

Efficient approach : Space optimization

In previous approach the current value dp[i][j] is only depend upon the current and previous row values of DP. So to optimize the space complexity we use a single 1D array to store the computations.

Implementation steps:

• Create a 1D vector prev of size n2+1 and initialize it with 0.
• Set a base case by initializing the values of prev.
• Now iterate over subproblems by the help of nested loop and get the current value from previous computations.
• Now Create a temporary 1d vector curr used to store the current values from previous computations.
• After every iteration assign the value of curr to prev for further iteration.
• At last return and print the final answer stored in prev[n2]

Implementation: 
 

// C++ program to count common subsequence in two strings #include <bits/stdc++.h> using namespace std; // return the number of common subsequence in // two strings int CommonSubsequencesCount(string s, string t) {  int n1 = s.length();  int n2 = t.length();    // to store previous computaions of subproblems  vector<int>prev(n2+1 , 0);  // for each character of S  for (int i = 1; i <= n1; i++) {  vector<int>curr(n2 +1 , 0);  // for each character in T  for (int j = 1; j <= n2; j++) {  // if character are same in both  // the string  if (s[i - 1] == t[j - 1])  curr[j] = 1 + curr[j - 1] + prev[j];   else  curr[j] = curr[j - 1] + prev[j] - prev[j - 1];   }    // assigning values   // for iterate further  prev = curr;  }    // return final answer  return prev[n2]; } // Driver Program int main() {  string s = "ajblqcpdz";  string t = "aefcnbtdi";  cout << CommonSubsequencesCount(s, t) << endl;  return 0; } 

import java.util.*; public class Main {  // Function to count the number of common subsequences in two strings  public static int CommonSubsequencesCount(String s, String t) {  int n1 = s.length();  int n2 = t.length();  // To store previous computations of subproblems  int[] prev = new int[n2 + 1];  // For each character of S  for (int i = 1; i <= n1; i++) {  int[] curr = new int[n2 + 1];  // For each character in T  for (int j = 1; j <= n2; j++) {  // If characters are same in both the strings  if (s.charAt(i - 1) == t.charAt(j - 1)) {  curr[j] = 1 + curr[j - 1] + prev[j];  } else {  curr[j] = curr[j - 1] + prev[j] - prev[j - 1];  }  }  // Assigning values for further iterations  prev = curr;  }  // Return the final answer  return prev[n2];  }  // Driver program  public static void main(String[] args) {  String s = "ajblqcpdz";  String t = "aefcnbtdi";  System.out.println(CommonSubsequencesCount(s, t));  } } 

using System; public class CommonSubsequenceCount {  // return the number of common subsequence in  // two strings  public static int Count(string s, string t)  {  int n1 = s.Length;  int n2 = t.Length;  // to store previous computations of subproblems  int[] prev = new int[n2 + 1];  // for each character of S  for (int i = 1; i <= n1; i++) {  int[] curr = new int[n2 + 1];  // for each character in T  for (int j = 1; j <= n2; j++) {  // if characters are the same in both  // strings  if (s[i - 1] == t[j - 1])  curr[j] = 1 + curr[j - 1] + prev[j];  else  curr[j] = curr[j - 1] + prev[j]  - prev[j - 1];  }  // assign values for further iteration  prev = curr;  }  // return final answer  return prev[n2];  }  public static void Main()  {  string s = "ajblqcpdz";  string t = "aefcnbtdi";  Console.WriteLine(Count(s, t));  } } 

// Javascript program to count common subsequence in two strings // return the number of common subsequence in // two strings function CommonSubsequencesCount(s, t) {  let n1 = s.length;  let n2 = t.length;    // to store previous computaions of subproblems  let prev = new Array(n2+1).fill(0);    // for each character of s  for (let i = 1; i <= n1; i++) {  let curr = new Array(n2 + 1).fill(0);  // for each character in t  for (let j = 1; j <= n2; j++) {  // if character are same in both  // the string  if (s[i - 1] === t[j - 1])  curr[j] = 1 + curr[j - 1] + prev[j];   else  curr[j] = curr[j - 1] + prev[j] - prev[j - 1];   }  // assigning values   // for iterate further  prev = curr;  }  // return final answer  return prev[n2]; } // Driver Program let s = "ajblqcpdz"; let t = "aefcnbtdi"; console.log(CommonSubsequencesCount(s, t)); 

def CommonSubsequencesCount(s, t): n1 = len(s) n2 = len(t) # to store previous computations of subproblems prev = [0] * (n2 + 1) # for each character of S for i in range(1, n1 + 1): curr = [0] * (n2 + 1) # for each character in T for j in range(1, n2 + 1): # if characters are the same in both strings if s[i - 1] == t[j - 1]: curr[j] = 1 + curr[j - 1] + prev[j] else: curr[j] = curr[j - 1] + prev[j] - prev[j - 1] # assigning values for iteration prev = curr # return the final answer return prev[n2] # Driver Program if __name__ == "__main__": s = "ajblqcpdz" t = "aefcnbtdi" print(CommonSubsequencesCount(s, t)) 

11

Time Complexity : O(n1 * n2) 
Auxiliary Space : O(n2)