There are many problems in which we require to get all K-length substrings of a string. This particular utility is very popular in competitive programming and having shorthands to solve this problems 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 a brute-force method to perform this task.
Python3
# Python3 code to demonstrate working of # Extract K length substrings # using list comprehension + string slicing # Initializing string test_str = "Geeks"# Printing original string print("The original string is : " + str(test_str)) # Initializing K K = 3# Extract K length substrings # using list comprehension + string slicing res = [test_str[i: j] for i in range(len(test_str)) for j in range(i + 1, len(test_str) + 1) if len(test_str[i:j]) == K] # Printing result print("All K length substrings of string are : " + str(res)) |
The original string is : Geeks All K length substrings of string are : ['Gee', 'eek', 'eks']
Time Complexity: O(n2)
Auxiliary Space: O(n)
Method #2: Using itertools.combinations()
This particular task can also be performed using the inbuilt function of combinations, which helps to get all K lengths of the possible combinations i.e. the substrings from a string.
Python3
# Python3 code to demonstrate working of# Extract K length substrings# using itertools.combinations()from itertools import combinations# Initializing stringtest_str = "Geeks"# Printing original stringprint("The original string is : " + str(test_str))# Initializing KK = 3# Extract K length substrings# using itertools.combinations()res = [test_str[x:y] for x, y in combinations( range(len(test_str) + 1), r=2) if len(test_str[x:y]) == K]# Printing resultprint("All K length substrings of string are : " + str(res)) |
The original string is : Geeks All K length substrings of string are : ['Gee', 'eek', 'eks']
Time Complexity: O(n2) -> (loop+combinations)
Auxiliary Space: O(n)
Method #3: Using a for loop
Stepwise approach:
- Initialize an empty list to store the K length substrings
- Loop through the range from 0 to the length of the string minus K (i.e. up to the last possible starting index for a substring of length K)
- For each index i in the range, append the substring starting at index i and ending at i+K to the list
- Print the list of K length substrings
Below is the implementation of the above approach:
Python3
# Initializing list and value test_str = "Geeks"print("The original string is : " + str(test_str)) K = 3# Extracting K length substrings using for loopres = []for i in range(len(test_str) - K + 1): res.append(test_str[i:i+K])# Printing answer print("All K length substrings of string are : " + str(res)) |
The original string is : Geeks All K length substrings of string are : ['Gee', 'eek', 'eks']
Time complexity: O(nK), where n is the length of the string and K is the length of the desired substrings.
Auxiliary space: O(nK), as the list of substrings can potentially hold n/K elements, each with K character
Method #6: Using recursion
We can also solve this problem using recursion. We can define a recursive function that takes the input string and the desired substring length as arguments. The function will return a list of all substrings of the given length in the input string.
Stepwise approach:
- Define a recursive function get_substrings() that takes the input string and the desired substring length as arguments.
- Base case: if the length of the input string is less than the desired substring length, return an empty list.
- Recursive case: append the first substring of the desired length to the result list, and recursively call the function on the remaining string.
- Return the result list.
Below is the implementation of the above approach:
Python3
def get_substrings(s, k): if len(s) < k: return [] else: return [s[:k]] + get_substrings(s[1:], k)# Example usagetest_str = "Geeks"K = 3substrings = get_substrings(test_str, K)print("All K length substrings of string are : " + str(substrings)) |
All K length substrings of string are : ['Gee', 'eek', 'eks']
Time complexity: O(n * K), where n is the length of the given string and K is the desired substring length. This is because the function makes n/K recursive calls, each of which requires slicing a substring of length K from the input string, which takes O(K) time.
Auxiliary space: O(n/K), as the function creates a new list for each recursive call, each of which contains at most one substring of length K.
Method #4: Using sliding window technique
The sliding window technique involves defining a window of size K and sliding it over the given string, extracting substrings of length K at each step. Here’s the step-by-step approach:
- Initialize an empty list to store the K-length substrings.
- Define a window of size K and slide it over the string until it reaches the end.
- Extract the substring within the window and append it to the list.
- Return the list of K-length substrings.
Python3
# Python3 code to demonstrate working of # Extract K length substrings # using sliding window technique # Initializing string test_str = "Geeks"# Printing original string print("The original string is : " + str(test_str)) # Initializing K K = 3# Extract K length substrings # using sliding window techniqueres = []for i in range(len(test_str) - K + 1): res.append(test_str[i:i+K])# Printing result print("All K length substrings of string are : " + str(res)) |
The original string is : Geeks All K length substrings of string are : ['Gee', 'eek', 'eks']
Time complexity: O(n-k+1) where n is the length of the string and k is the length of the substring to be extracted.
Auxiliary space: O(n-k+1) to store the list of K-length substrings.
Method #7: Using a generator function
Step-by-step approach:
- Initialize the given string and initialize the value of K.
- Define a generator function called k_length_substrings that takes in the string s and the value of k.
- The generator function yields K-length substrings by iterating over the indices of the string up to the last Kth index and slicing the string from that index to the Kth index.
- Extract K length substrings by calling the generator function with the given string and K, and store the results in the res list.
- Print the results.
Python3
# Python3 code to demonstrate working of# Extract K length substrings# Using a generator function# initializing stringtest_str = "Geeks"# printing original stringprint("The original string is : " + str(test_str))# initializing KK = 3# generator function to yield K length substringsdef k_length_substrings(s, k): for i in range(len(s)-k+1): yield s[i:i+k]# Extract K length substringsres = list(k_length_substrings(test_str, K))# printing resultprint("All K length substrings of string are : " + str(res)) |
The original string is : Geeks All K length substrings of string are : ['Gee', 'eek', 'eks']
Time complexity: O(NK), where n is the length of the string and k is the length of the substring.
Auxiliary space: O(K), where k is the length of the substring (for the generator function).
