Given a string, the task is to write a Python program to find all combinations of overlapping substrings of a string and store it in a list. The list of lists will be ordered and grouped by length of substrings.
Input : test_str = ‘Geeks4G’
Output : [[”, ”, ”, ”, ”, ”, ”, ”], [‘G’, ‘e’, ‘e’, ‘k’, ‘s’, ‘4’, ‘G’], [‘Ge’, ‘ee’, ‘ek’, ‘ks’, ‘s4’, ‘4G’], [‘Gee’, ‘eek’, ‘eks’, ‘ks4’, ‘s4G’], [‘Geek’, ‘eeks’, ‘eks4’, ‘ks4G’], [‘Geeks’, ‘eeks4’, ‘eks4G’], [‘Geeks4’, ‘eeks4G’], [‘Geeks4G’]]
Explanation : All lengths overlapping substrings extracted.
Input : test_str = ‘Geeks’
Output : [[”, ”, ”, ”, ”, ”], [‘G’, ‘e’, ‘e’, ‘k’, ‘s’], [‘Ge’, ‘ee’, ‘ek’, ‘ks’], [‘Gee’, ‘eek’, ‘eks’], [‘Geek’, ‘eeks’], [‘Geeks’]]
Explanation : All lengths overlapping substrings extracted.
Method : Using list comprehension, slicing and loop
In this, we perform task of getting each slice using slicing, all the strings of particular size is created using list comprehension. Manipulation of all sizes is done using loop. Later all are printed as a list of lists.
Example:
Python3
# Python3 code to demonstrate working of# Overlapping substrings of all lengths# Using list comprehension + slicing + loop# initializing stringtest_str = 'Geeks4G'# printing original stringprint("The original string is : " + str(test_str))# manipulating overlap size using loopres = []for idx in range(len(test_str) + 1): # getting overlap strings res.append([test_str[j: j + idx] for j in range(len(test_str) - idx + 1)])# printing resultprint("All overlapping Strings : " + str(res)) |
Output:
The original string is : Geeks4G
All overlapping Strings : [[”, ”, ”, ”, ”, ”, ”, ”], [‘G’, ‘e’, ‘e’, ‘k’, ‘s’, ‘4’, ‘G’], [‘Ge’, ‘ee’, ‘ek’, ‘ks’, ‘s4’, ‘4G’], [‘Gee’, ‘eek’, ‘eks’, ‘ks4’, ‘s4G’], [‘Geek’, ‘eeks’, ‘eks4’, ‘ks4G’], [‘Geeks’, ‘eeks4’, ‘eks4G’], [‘Geeks4’, ‘eeks4G’], [‘Geeks4G’]]
Time Complexity: O(n2)
Space Complexity: O(n)
