Count common sub-sequences in two strings in Python

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 Python.

Method 1: Using Recursion

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

def count_subsequences(str1, str2, m, n):
    if m == 0 or n == 0:
        return 0
    if str1[m - 1] == str2[n - 1]:
        return 1 + count_subsequences(str1, str2, m - 1, n - 1)
    else:
        return count_subsequences(str1, str2, m - 1, n) + count_subsequences(str1, str2, m, n - 1)

str1 = "abc"
str2 = "ac"
print("Common Subsequences Count:", count_subsequences(str1, str2, len(str1), len(str2)))

Input: abc, ac
Output: Common Subsequences Count: 3

Method 2: Using Dynamic Programming

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

def dp_subsequences(str1, str2):
    m, n = len(str1), len(str2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i - 1] == str2[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]

str1 = "abc"
str2 = "ac"
print("Common Subsequences Count:", dp_subsequences(str1, str2))

Input: abc, ac
Output: Common Subsequences Count: 3

Method 3: Using Bitmasking

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

def count_with_bitmask(str1, str2):
    count = 0
    len1 = len(str1)
    for i in range(1 << len1):
        sub1 = "".join(str1[j] for j in range(len1) if (i & (1 << j)) != 0)
        if sub1 in str2:
            count += 1
    return count

str1 = "abc"
str2 = "ac"
print("Common Subsequences Count:", count_with_bitmask(str1, str2))

Input: abc, ac
Output: Common Subsequences Count: 3