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 stringsint 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 Programint main(){ string s = "ajblqcpdz"; string t = "aefcnbtdi"; cout << CommonSubsequencesCount(s, t) << endl; return 0;} |
Java
// Java program to count common subsequence in two stringspublic 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 stringsdef 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 Codes = "ajblqcpdz"t = "aefcnbtdi"print(CommonSubsequencesCount(s, t))# This code is contributed by Mohit Kumar |
C#
// C# program to count common // subsequence in two stringsusing 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 stringsfunction 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 Programvar 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 stringsfunction 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
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++
// C++ program to count common subsequence in two strings#include <bits/stdc++.h>using namespace std;// return the number of common subsequence in// two stringsint 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 Programint 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 Programif __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 stringsfunction 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 Programlet s = "ajblqcpdz";let t = "aefcnbtdi";console.log(CommonSubsequencesCount(s, t)); |
Output
11
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
