Thursday, September 4, 2025
HomeLanguagesPython Program To Get Minimum Elements For String Construction

Python Program To Get Minimum Elements For String Construction

Given a String, the task is to write a Python program to count the minimum elements required to form a string from list elements.

Input : test_list = [“geek”, “ring”, “sfor”, “ok”, “woke”], tar_str = “working” 
Output : 2 
Explanation : working can be formed using woke and ring.

Input : test_list = [“geek”, “ring”, “sfor”, “ok”, “woke”], tar_str = “workinggeek” 
Output : 3 
Explanation : workinggeek can be formed using woke, geek and ring. 
 

Method : Using issubset() + set() + combinations()

In this, we iterate for a list of strings and form all size combinations, each combination is converted to set and checked to be forming target string using issubset(), if found, the loop is exited and the count is recorded.

Python3




# Python3 code to demonstrate working of
# Minimum elements for String construction
# Using issubset() + set() + combinations()
from itertools import combinations
 
# initializing list
test_list = ["geek", "ring", "sfor", "ok", "woke"]
 
# printing original list
print("The original list is : " + str(test_list))
 
# initializing target string
tar_str = "working"
 
res = -1
set_str = set(tar_str)
done = False
for val in range(0, len(test_list) + 1):
     
    # creating combinations
    for sub in combinations(test_list, val):
         
        # constructing sets of each combinations
        temp_set = set(ele for subl in sub for ele in subl)
         
        # checking if target string has created set as subset
        if set_str.issubset(temp_set):
            res = val
            done = True
            break
    if done:
        break
 
# printing result
print("The Minimum count elements for string : " + str(res))


Output

The original list is : ['geek', 'ring', 'sfor', 'ok', 'woke']
The Minimum count elements for string : 2

Time Complexity: O(n2)
Auxiliary Space: O(n)

Method : using set intersection.

This method involves converting the target string into a set and then iterating over the list of strings. For each string in the list, convert it into a set and find its intersection with the target set. If the size of the intersection is equal to the size of the current string, it means that all characters of the current string are present in the target string and hence the current string can be used to construct the target string.

Here’s the code for this approach:

Python3




def get_min_elements(test_list, tar_str):
    set_str = set(tar_str)
    count = 0
    for string in test_list:
        set_string = set(string)
        if len(set_str & set_string) == len(string):
            count += 1
            set_str -= set_string
    return count
 
test_list = ["geek", "ring", "sfor", "ok", "woke"]
tar_str = "working"
print(get_min_elements(test_list, tar_str))


Output

2

Time Complexity: O(n * m) where n is the length of the target string and m is the number of strings in the list.

Auxiliary Space: O(n + m)

Dominic
Dominichttp://wardslaus.com
infosec,malicious & dos attacks generator, boot rom exploit philanthropist , wild hacker , game developer,
RELATED ARTICLES

Most Popular

Dominic
32264 POSTS0 COMMENTS
Milvus
81 POSTS0 COMMENTS
Nango Kala
6632 POSTS0 COMMENTS
Nicole Veronica
11800 POSTS0 COMMENTS
Nokonwaba Nkukhwana
11860 POSTS0 COMMENTS
Shaida Kate Naidoo
6749 POSTS0 COMMENTS
Ted Musemwa
7025 POSTS0 COMMENTS
Thapelo Manthata
6698 POSTS0 COMMENTS
Umr Jansen
6718 POSTS0 COMMENTS