Count common sub-sequences in two strings in Java

Understanding Common Subsequences

A common subsequence of two strings is a sequence that appears in both strings in the same relative order but not necessarily contiguously.

We will explore three different methods to count common sub-sequences in two strings using Java.

Method 1: Using Recursion

This method recursively finds the count of common sub-sequences.

public class CommonSubsequences {
    public static int countSubsequences(String str1, String str2, int m, int n) {
        if (m == 0 || n == 0)
            return 0;
        if (str1.charAt(m - 1) == str2.charAt(n - 1))
            return 1 + countSubsequences(str1, str2, m - 1, n - 1);
        else
            return countSubsequences(str1, str2, m - 1, n) + countSubsequences(str1, str2, m, n - 1);
    }
    public static void main(String[] args) {
        String str1 = "abc";
        String str2 = "ac";
        System.out.println("Common Subsequences Count: " + countSubsequences(str1, str2, str1.length(), str2.length()));
    }
}
            

Method 2: Using Dynamic Programming

This method uses a DP table to count common sub-sequences efficiently.

public class DPSubsequences {
    public static int dpSubsequences(String str1, String str2) {
        int m = str1.length(), n = str2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0)
                    dp[i][j] = 0;
                else if (str1.charAt(i - 1) == str2.charAt(j - 1))
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                else
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
    public static void main(String[] args) {
        String str1 = "abc";
        String str2 = "ac";
        System.out.println("Common Subsequences Count: " + dpSubsequences(str1, str2));
    }
}
            

Method 3: Using Bitmasking

This method uses bitwise operations to find the count of common sub-sequences.

public class BitmaskSubsequences {
    public static int countWithBitmask(String str1, String str2) {
        int count = 0;
        int len1 = str1.length(), len2 = str2.length();
        for (int i = 0; i < (1 << len1); i++) {
            StringBuilder sub1 = new StringBuilder();
            for (int j = 0; j < len1; j++) {
                if ((i & (1 << j)) != 0) sub1.append(str1.charAt(j));
            }
            if (str2.contains(sub1.toString()))
                count++;
        }
        return count;
    }
    public static void main(String[] args) {
        String str1 = "abc";
        String str2 = "ac";
        System.out.println("Common Subsequences Count: " + countWithBitmask(str1, str2));
    }
}