Python – Filter Strings combination of K substrings

Last Updated : 07 Apr, 2023

Given a Strings list, extract all the strings that are a combination of K substrings.

Input : test_list = [“geeks4u”, “allbest”, “abcdef”], substr_list = [“s4u”, “est”, “al”, “ge”, “ek”, “def”], K = 3

Output : [‘geeks4u’]

Explanation : geeks4u made up of 3 substr – ge, ek and s4u.

Input : test_list = [“geeks4u”, “allbest”, “abcdef”], substr_list = [“s4u”, “est”, “al”, “ge”, “def”, ‘lb’], K = 3

Output : [‘allbest’]

Explanation : allbest made up of 3 substr – al, lb and est.

Method #1 : Using permutations() + map() + join() + set() + loop

In this, we perform this task by getting all possible permutation of K substrings from substring list, and then perform task of join using join and map(). The set() is used to avoid duplication. At last, match from Strings list is done using loop.

Python3

# Python3 code to demonstrate working of 
# Filter Strings  combination of K substrings
# Using permutations() + map() + join() + set() + loop
from itertools import permutations
 
# initializing list
test_list = ["geeks4u", "allbest", "abcdef"]
 
# printing string
print("The original list : " + str(test_list))
 
# initializing substring list
substr_list = ["s4u", "est", "al", "ge", "ek", "def", "lb"]
 
# initializing K 
K = 3
 
# getting all permutations
perms = list(set(map(''.join, permutations(substr_list, r = K))))
 
# using loop to check permutations with list
res = []
for ele in perms:
    if ele in test_list:
        res.append(ele)
 
# printing results 
print("Strings after joins : " + str(res))

Output

The original list : ['geeks4u', 'allbest', 'abcdef']
Strings after joins : ['geeks4u', 'allbest']

Method #2 : Using intersection()

This uses all functions of the above method, the last task of matching permutation list and original list is done by intersection.

Python3

# Python3 code to demonstrate working of 
# Filter Strings  combination of K substrings
# Using permutations() + map() + join() + set() + intersection()
from itertools import permutations
 
# initializing list
test_list = ["geeks4u", "allbest", "abcdef"]
 
# printing string
print("The original list : " + str(test_list))
 
# initializing substring list
substr_list = ["s4u", "est", "al", "ge", "ek", "def", "lb"]
 
# initializing K 
K = 3
 
# getting all permutations
perms = set(map(''.join, permutations(substr_list, r = K)))
 
# using intersection() to solve this problem 
res = list(set(test_list).intersection(perms))
 
# printing results 
print("Strings after joins : " + str(res))

Output

The original list : ['geeks4u', 'allbest', 'abcdef']
Strings after joins : ['geeks4u', 'allbest']

The Time and Space Complexity for all the methods are the same:

Time Complexity: O(n)

Auxiliary Space: O(n)

Method 3: Using nested loops to generate permutations and checking for matches.

Algorithm:
1. Import the `permutations()` function from `itertools`.
2. Define the given `test_list`, `substr_list`, and `K`.
3. Initialize an empty list `res`.
4. Loop through each string `s` in `test_list`.
5. Loop through each permutation `p` of length `K` in `substr_list`.
6. Check if the joined permutation `p` is a substring of the current string `s`.
7. If it is, append the string `s` to the `res` list and break out of the loop over permutations.
8. Print the resulting list `res` of strings that contain at least one combination of `K` substrings from `substr_list`.

Python3

from itertools import permutations
 
test_list = ["geeks4u", "allbest", "abcdef"]
substr_list = ["s4u", "est", "al", "ge", "ek", "def", "lb"]
K = 3
print("The original list : " + str(test_list))
 
res = []
for s in test_list:
    for p in permutations(substr_list, K):
        if ''.join(p) in s:
            res.append(s)
            break
 
print("Strings after joins : " + str(res))

Output

The original list : ['geeks4u', 'allbest', 'abcdef']
Strings after joins : ['geeks4u', 'allbest']

The time complexity of this algorithm is O(n*k! * m), where n is the length of `test_list`, k is the length of each permutation (which is a constant `K` in this case), and m is the maximum length of any string in `test_list`.
The auxiliary space of this algorithm is also O(n * m), since we need to store the resulting list `res` of strings that match the condition. The space complexity of the `permutations()` function is O(k!), which is a constant.