There are many problems in which we require to get all substrings of a string. This particular utility is very popular in competitive programming and having shorthands to solve this problem can always be handy. Let’s discuss certain ways in which this problem can be solved.
Method #1 : Using list comprehension + string slicing The combination of list comprehension and string slicing can be used to perform this particular task. This is just brute force method to perform this task.
Python3
# Python3 code to demonstrate working of# Get all substrings of string# Using list comprehension + string slicing# initializing stringtest_str = "Geeks"# printing original stringprint("The original string is : " + str(test_str))# Get all substrings of string# Using list comprehension + string slicingres = [test_str[i: j] for i in range(len(test_str)) for j in range(i + 1, len(test_str) + 1)]# printing resultprint("All substrings of string are : " + str(res)) |
The original string is : Geeks All substrings of string are : [‘G’, ‘Ge’, ‘Gee’, ‘Geek’, ‘Geeks’, ‘e’, ‘ee’, ‘eek’, ‘eeks’, ‘e’, ‘ek’, ‘eks’, ‘k’, ‘ks’, ‘s’]
Method #2 : Using itertools.combinations() This particular task can also be performed using the inbuilt function of combinations, which helps to get all the possible combinations i.e the substrings from a string.
Python3
# Python3 code to demonstrate working of# Get all substrings of string# Using itertools.combinations()from itertools import combinations# initializing stringtest_str = "Geeks"# printing original stringprint("The original string is : " + str(test_str))# Get all substrings of string# Using itertools.combinations()res = [test_str[x:y] for x, y in combinations( range(len(test_str) + 1), r = 2)]# printing resultprint("All substrings of string are : " + str(res)) |
The original string is : Geeks All substrings of string are : [‘G’, ‘Ge’, ‘Gee’, ‘Geek’, ‘Geeks’, ‘e’, ‘ee’, ‘eek’, ‘eeks’, ‘e’, ‘ek’, ‘eks’, ‘k’, ‘ks’, ‘s’]
Method #3 : Using recursion
This code defines a recursive function get_all_substrings() that takes an input string and returns a list of all possible substrings of the input string. The function first checks for two base cases: if the input string is empty, it returns an empty list; if the input string contains only one character, it returns a list containing that character. If the input string contains multiple characters, the function creates an empty list to store the resulting substrings, and uses nested loops to generate all possible substrings of the input string. Finally, the function recursively calls itself with the input string sliced from the second character to the end, and concatenates the resulting list of substrings with the list of substrings generated from the current call. The resulting list of substrings is returned as the final output.
Python3
def get_all_substrings(input_string): # base case 1: if the input string is empty, return an empty list if len(input_string) == 0: return [] # base case 2: if the input string contains only one character, return a list with that character elif len(input_string) == 1: return [input_string] # recursive case: if the input string contains multiple characters else: # create an empty list to store the resulting substrings output = [] # use nested loops to generate all possible substrings of the input string for i in range(len(input_string)): for j in range(i+1, len(input_string)+1): output.append(input_string[i:j]) # recursively call the function with the input string sliced from the second character to the end # and concatenate the resulting list of substrings with the list generated from the current call return output + get_all_substrings(input_string[1:])# test the function with an example stringmy_string = "hello"substrings = get_all_substrings(my_string)print(substrings) |
['h', 'he', 'hel', 'hell', 'hello', 'e', 'el', 'ell', 'ello', 'l', 'll', 'llo', 'l', 'lo', 'o', 'e', 'el', 'ell', 'ello', 'l', 'll', 'llo', 'l', 'lo', 'o', 'l', 'll', 'llo', 'l', 'lo', 'o', 'l', 'lo', 'o', 'o']
Time complexity: O(n^3)
Auxiliary space: O(n^2)
Method #4: Using numpy:
Algorithm:
1.Initialize an empty numpy array.
2.Loop through each index i in the range [0, len(test_str)), and for each i, loop through each index j in the range [i+1, len(test_str)+1).
3.Append the substring from index i to j to the numpy array.
4.Sort the numpy array by length and alphabetically, and remove duplicates.
5.Print the resulting array of substrings.
Python3
import numpy as nptest_str = "Geeks"# printing original stringprint("The original string is : " + str(test_str))# get all possible substringsres = np.array([test_str[i:j] for i in range(len(test_str)) for j in range(i+1, len(test_str)+1)])# sort substrings by length and alphabeticallyres = np.unique(np.sort(res, axis=0), axis=0)# printing resultprint("All substrings of string are : " + str(res))#This code is contributed by Jyothi pinjala. |
Output:
The original string is : Geeks All substrings of string are : ['G' 'Ge' 'Gee' 'Geek' 'Geeks' 'e' 'ee' 'eek' 'eeks' 'ek' 'eks' 'k' 'ks' 's']
Time complexity: O(n^2 log n), where n is the length of the input string. This is because we have two nested loops that iterate over n elements each, and then we sort the resulting numpy array which takes O(n log n) time.
Space complexity: O(n^2), because we are storing all possible substrings in a numpy array of size n^2.
Method 5: Using a nested loop
Python3
# Python3 code to demonstrate working of# Get all substrings of string# Using nested loops# initializing stringtest_str = "Geeks"# printing original stringprint("The original string is : " + str(test_str))# Get all substrings of string# Using nested loopsres = []for i in range(len(test_str)): for j in range(i+1, len(test_str)+1): res.append(test_str[i:j])# printing resultprint("All substrings of string are : " + str(res)) |
The original string is : Geeks All substrings of string are : ['G', 'Ge', 'Gee', 'Geek', 'Geeks', 'e', 'ee', 'eek', 'eeks', 'e', 'ek', 'eks', 'k', 'ks', 's']
Time complexity: O(n^3), where n is the length of the string, since there are two nested loops and each iteration involves slicing the string.
Auxiliary space: O(n^2), since that is the maximum number of substrings that can be generated for a string of length n.
Method #6: Using regex to generate all possible substrings:
Step by step algorithm:
- Import the ‘re’ module for regular expressions.
- Initialize a string variable ‘test_str’ with the value “Geeks”.
- Create an empty list ‘res’ to store the substrings.
- Start a for loop from i = 0 to length of the string – 1.
- Inside the first loop, start a nested for loop from j = i+1 to length of the string.
- Use string slicing to get the substring from index i to j and store it in a variable.
- Remove any non-alphanumeric characters from the substring using the ‘re.sub()’ method and store the result in the ‘res’ list.
- Print the result.
Python3
import re # Importing the regular expression moduletest_str = "Geeks"res = [] # Initialize an empty list to store the substringsfor i in range(len(test_str)): for j in range(i+1, len(test_str)+1): # Use string slicing to get the substring and remove any non-alphanumeric characters using regular expression res.append(re.sub(r'\W+', '', test_str[i:j]))print("All substrings of string are: " + str(res)) # Print the result |
All substrings of string are: ['G', 'Ge', 'Gee', 'Geek', 'Geeks', 'e', 'ee', 'eek', 'eeks', 'e', 'ek', 'eks', 'k', 'ks', 's']
Time complexity: O(n^2), where n is the length of the input string.
Space complexity: O(n^2), where n is the length of the input string.
