Python Program to split string into k sized overlapping strings
Given a string, the task is to write a Python program to extract overlapping consecutive string slices from the original string according to size K.
Example:
Input : test_str = ‘w3wiki’, K = 4
Output : [‘Geek’, ‘eeks’, ‘eksf’, ‘ksfo’, ‘sfor’, ‘forg’, ‘orge’, ‘rgee’, ‘geek’, ‘eeks’]
Explanation : Consecutive overlapping 4 sized strings are output.
Input : test_str = ‘w3wiki’, K = 6
Output : [‘Beginnerf’, ‘eeksfo’, ‘eksfor’, ‘ksforg’, ‘sforge’, ‘forgee’, ‘orgeek’, ‘rBeginner’]
Explanation : Consecutive overlapping 6 sized strings are output.
Method 1: Using islice() + generator function + join()
In this, windows of size K are extracted using the islice(), and results are yielded in an intermediate way using yield. The final results are joined using join().
Python3
# Python3 code to demonstrate working of # Overlapping consecutive K splits # Using islice() + generator function + join() from itertools import islice # generator function def over_slice(test_str, K): itr = iter (test_str) res = tuple (islice(itr, K)) if len (res) = = K: yield res for ele in itr: res = res[ 1 :] + (ele,) yield res # initializing string test_str = 'w3wiki' # printing original string print ( "The original string is : " + str (test_str)) # initializing K K = 4 # calling generator function res = ["".join(ele) for ele in over_slice(test_str, K)] # printing result print ( "Overlapping windows : " + str (res)) |
Output:
The original string is : w3wiki
Overlapping windows : [‘Geek’, ‘eeks’, ‘eksf’, ‘ksfo’, ‘sfor’, ‘forg’, ‘orge’, ‘rgee’, ‘geek’, ‘eeks’]
Method 2: Using list comprehension + slicing
In this example, intermediate slices are performed using a slicing operation in a more pythonic way. Each window is extracted using slice notation.
Python3
# Python3 code to demonstrate working of # Overlapping consecutive K splits # Using list comprehension + slicing # initializing string test_str = 'w3wiki' # printing original string print ( "The original string is : " + str (test_str)) # initializing K K = 4 # extracting window using slicing res = [test_str[idx:idx + K] for idx in range ( len (test_str) - K + 1 )] # printing result print ( "Overlapping windows : " + str (res)) |
Output:
The original string is : w3wiki
Overlapping windows : [‘Geek’, ‘eeks’, ‘eksf’, ‘ksfo’, ‘sfor’, ‘forg’, ‘orge’, ‘rgee’, ‘geek’, ‘eeks’]
The Time and Space Complexity of all the methods is :
Time Complexity: O(n)
Space Complexity: O(n)
Method 3: Using recursion :
Python3
# Python3 code to demonstrate working of # Overlapping consecutive K splits # Using recursion # initializing string test_str = 'w3wiki' # printing original string print ( "The original string is : " + str (test_str)) # initializing K K = 4 # recursive function def over_slice(test_str, K, res = []): # if length of string is less if ( len (test_str) < K): return # append the string res.append(test_str[:K]) # call recursively over_slice(test_str[ 1 :], K, res) # return result return res # calling recursive function res = over_slice(test_str, K) # printing result print ( "Overlapping windows : " + str (res)) #This code is contributed by Edula Vinay Kumar Reddy |
The original string is : w3wiki Overlapping windows : ['Geek', 'eeks', 'eksf', 'ksfo', 'sfor', 'forg', 'orge', 'rgee', 'geek', 'eeks']
Time Complexity: O(n)
Auxiliary Space: O(n)
Method 4 : using the windowed() function from the more_itertools module.
This function takes an iterable and a window size, and returns an iterator over overlapping windows of the specified size.
The steps for this approach are:
Import the windowed() function from the more_itertools module.
Initialize a list containing the string to be split.
Use the windowed() function to get an iterator over overlapping windows of size K.
Use a list comprehension to join each window of characters into a string.
Return the list of overlapping windows.
Python3
# Python3 code to demonstrate working of # Overlapping consecutive K splits # Using windowed() function from more_itertools module from more_itertools import windowed # initializing string test_str = 'w3wiki' # printing original string print ( "The original string is : " + str (test_str)) # initializing K K = 4 # converting string to list of characters str_list = list (test_str) # using windowed() function to get overlapping windows windows = windowed(str_list, K, step = 1 ) # using list comprehension to join windows into strings res = ["".join(w) for w in windows] # printing result print ( "Overlapping windows : " + str (res)) |
OUTPUT : The original string is : w3wiki Overlapping windows : ['Geek', 'eeks', 'eksf', 'ksfo', 'sfor', 'forg', 'orge', 'rgee', 'geek', 'eeks']
The time complexity of this approach is O(N), since the windowed() function is a generator and only generates the windows as they are needed, without precomputing them all at once.
The auxiliary space complexity is O(NK), since we need to store all the overlapping windows in a list.