Count common subsequence in two strings

0 0 9 minutes read

Given two string S and Q. 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++

// 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

// 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
}

Python3

# 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

C#

// 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

Javascript

<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
// 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
?>

Output

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++

// 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;
}

Java

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

Python3

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))

C#

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

// 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));

Output

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

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!