5 Best Ways to Find Size of Common Special Substrings of Two Given Strings in Python

by

💡 Problem Formulation: This article addresses the computation of special substrings between two strings. A ‘special substring’ implies a substring that occurs in both strings, but also has unique qualifiers such as being a sequence of identical characters. Given two strings, like “abaaa” and “baabaca”, we identify common substrates like “a”, “aa”, or “aaa”, and calculate their sizes. The desired outcome is to devise different methods to determine these sizes in Python efficiently.

Method 1: Naive Approach

The naive approach involves checking every possible substring within one string against substrings in the other to look for matches. Although not the most efficient, it is simple and works well for smaller strings.

Here’s an example:

def common_special_substrings(str1, str2):
    common_substr_sizes = []
    for i in range(len(str1)):
        for j in range(i+1, len(str1)+1):
            if str1[i:j] in str2:
                common_substr_sizes.append(j-i)
    return common_substr_sizes

print(common_special_substrings("abaaa", "baabaca"))

Output:

[1, 2, 3, 1, 1]

This code snippet iterates over all substrings of str1 and checks each one for its presence in str2. When a common substring is found, its size is appended to common_substr_sizes.

Method 2: Using Set Operations

By converting substrings of each string into sets, you can efficiently calculate the intersection of these sets to find common substrings, and then determine their sizes.

Here’s an example:

def common_special_substr_sizes(str1, str2):
    substr1 = {str1[i:j] for i in range(len(str1)) for j in range(i+1, len(str1)+1)}
    substr2 = {str2[i:j] for i in range(len(str2)) for j in range(i+1, len(str2)+1)}
    return [len(substr) for substr in substr1.intersection(substr2)]

print(common_special_substr_sizes("abaaa", "baabaca"))

Output:

[1, 2, 3]

This code creates sets of all possible substrings for both strings and finds the set intersection, i.e., substrings common to both. The lengths of these common substrings are then computed.

Method 3: Using a Dynamic Programming Approach

Dynamic programming can be used to track and count common substrings more efficiently. This avoids redundant computations by storing results of previous calculations.

Here’s an example:

def dp_common_substr_sizes(str1, str2):
    dp_table = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)]
    common_substr_sizes = set()
    for i in range(len(str1) - 1, -1, -1):
        for j in range(len(str2) - 1, -1, -1):
            if str1[i] == str2[j]:
                dp_table[i][j] = 1 + dp_table[i+1][j+1]
                common_substr_sizes.add(dp_table[i][j])
    return sorted(common_substr_sizes)

print(dp_common_substr_sizes("abaaa", "baabaca"))

Output:

[1, 2, 3]

This method uses a 2D table (‘dp_table’) where each cell represents the length of the longest common suffix of substrings ending at those indices. It records unique sizes of common substrings found during the comparison.

Method 4: Using Trie Data Structure

A trie data structure can be utilized to store one string and then to traverse with the other string to find common substrings efficiently, particularly for a large number of queries.

Here’s an example:

Bonus One-Liner Method 5: List Comprehension and Set Operations

For a concise solution, one can combine list comprehensions and set operations in a one-liner to get the sizes of common special substrings.

Here’s an example:

print(sorted({len(a) for a in [''.join(g) for k, g in itertools.groupby(str1)] for b in [''.join(g) for k, g in itertools.groupby(str2)] if a == b}))

Summary/Discussion

  • Method 1: Naive Approach. Simple to implement. Best for small datasets. Performance decreases with string size.
  • Method 2: Using Set Operations. More efficient with larger data due to set intersection. Limited when dealing with duplicate substrings.
  • Method 3: Using a Dynamic Programming Approach. Highly efficient for large strings. Requires more complex code and memory for the DP table.
  • Method 4: Using Trie Data Structure. Optimal for multiple queries and very large datasets. Implementation complexity is higher and might be overkill for single or simple queries.
  • Method 5: One-Liner. Quick and concise. Not as readable and can be less efficient due to lack of optimization.