Job Updates
Interviews
Connect
Connect & get Notified

Count the Common Subsequences in two String

Program to check : Count the Common Subsequences in two String

Definition & Explanation

Counting common subsequences in two strings involves finding all subsequences that are present in both strings and counting them. A subsequence of a string is a new string that is formed from the original string by deleting some (or none) of the characters without changing the relative order of the remaining characters.

More Description

Program Logic

  1. Initialize a 2D array dp of size (m+1) x (n+1), where m and n are the lengths of the two strings.
  2. Iterate through each character of both strings.
  3. If the characters are equal, add 1 to the count of common subsequences ending at this character by adding dp[i-1][j-1] to dp[i][j].
  4. Otherwise, copy the count of common subsequences from the previous characters in either string (dp[i-1][j] and dp[i][j-1]) to dp[i][j].
  5. The result will be stored in dp[m][n].
C

Method 1 :

#include <iostream>
#include <cstring>
using namespace std;

int countCommonSubsequences(string s1, string s2) {
    int m = s1.length();
    int n = s2.length();
    int dp[m + 1][n + 1];
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m][n];
}

int main() {
    string s1 = "ABCBDAB";
    string s2 = "BDCAB";
    cout << "Count of common subsequences: " << countCommonSubsequences(s1, s2) << endl;
    return 0;
}

Output :

C++

Method 1 :

#include <iostream>
#include <cstring>
using namespace std;

int countCommonSubsequences(string s1, string s2) {
    int m = s1.length();
    int n = s2.length();
    int dp[m + 1][n + 1];
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m][n];
}

int main() {
    string s1 = "ABCBDAB";
    string s2 = "BDCAB";
    cout << "Count of common subsequences: " << countCommonSubsequences(s1, s2) << endl;
    return 0;
}

Output :

JAVA

Method 1 :

public class Main {
    static int countCommonSubsequences(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        String s1 = "ABCBDAB";
        String s2 = "BDCAB";
        System.out.println("Count of common subsequences: " + countCommonSubsequences(s1, s2));
    }
}

Output :

Python

Method 1 :

def count_common_subsequences(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

if __name__ == "__main__":
    s1 = "ABCBDAB"
    s2 = "BDCAB"
    print("Count of common subsequences:", count_common_subsequences(s1, s2))

Output :

View All Codes