Python – Consecutive element deletion strings

Sometimes, while working with Python, we can have a problem in which we have a string and wish to extract all possible combination of words after deletion of consecutive elements one at a time. This can have application in many domains. Lets discuss certain ways in which this task can be performed. 

Method #1 : Using list comprehension + list slicing This is one of the way in which this task can be performed. In this, we iterate for the elements of list and keep on creating new string using consecutive list slicing. 

Time Complexity: O(n), where n is the length of the input list. This is because we’re using list comprehension + list slicing which has a time complexity of O(n) in the worst case.
Auxiliary Space: O(n), as we’re using additional space res other than the input list itself with the same size of input list.

  Method #2 : Using list comprehension + enumerate() The combination of above methods can be used to perform this task. In this, we extract the index using enumerate. This gives more cleaner code. 

The Time and Space Complexity for all the methods are the same:

Time Complexity: O(n)

Space Complexity: O(n)

Method 3 Using a for loop.

Algorithm:

1. Take input string test_str and its length n.
2. Initialize an empty list res.
3. Using a for loop, iterate over the range of n.
4. In each iteration, append the string obtained by removing the character at that index to res.
5. Return the res list.

The original string is : Geeks4Geeks
Consecutive Elements removal list : ['eeks4Geeks', 'Geks4Geeks', 'Geks4Geeks', 'Gees4Geeks', 'Geek4Geeks', 'GeeksGeeks', 'Geeks4eeks', 'Geeks4Geks', 'Geeks4Geks', 'Geeks4Gees', 'Geeks4Geek']

Time Complexity: O(n^2), where n is the length of test_str.

Auxiliary Space: O(n), where n is the length of test_str. This is the space taken up by the res list.

Method 4: Using map() and lambda function

Algorithm

1. Initialize the string test_str.
2. Define a lambda function that takes a character in the string and returns the string with that character removed.
3. Use map() to apply the lambda function to each character in the string and return a list of strings.
4. Print the resultant list of strings.

The original string is : Geeks4Geeks
Consecutive Elements removal list : ['eeks4Geeks', 'Geks4Geeks', 'Geks4Geeks', 'Gees4Geeks', 'Geek4Geeks', 'GeeksGeeks', 'Geeks4eeks', 'Geeks4Geks', 'Geeks4Geks', 'Geeks4Gees', 'Geeks4Geek']

Time Complexity:

The lambda function takes constant time O(1) to execute.
The map() function applies the lambda function to each character in the string, which takes O(n) time, where n is the length of the string.
Therefore, the overall time complexity of this algorithm is O(n), where n is the length of the string.
Auxiliary Space:  O(n), where n is the length of the string, since we are storing the resultant list of strings in memory

Method 5: Using itertools and combinations:

1. First, we initialize the input string as test_str = ‘Geeks4Geeks’.
2. We print the original string.
3. We create an empty list res to store the results.
4. We iterate over the indices of the string using range(len(test_str)).
5. For each index i, we create a new string by concatenating the substring before i with the substring after i+1, and append it to the res list.
6. After the loop finishes, we print the res list which contains all the strings obtained by deleting consecutive characters in the input string.

...ek4Geeks', 'es4Geeks', 'eks4Geek', 'eks4Gees', 'eks4Geks', 'eks4Geks', 'eks4eeks', 'eksGeeks', 'ek4Geeks', 'es4Geeks', 'ks4Geeks', 'Geeks4Gee', 'Geeks4Gek', 'Geeks4Ges', 'Geeks4Gek', 'Geeks4Ges', 'Geeks4Gks', 'Geeks4eek', 'Geeks4ees', 'Geeks4eks', 'Geeks4eks', 'GeeksGeek', 'GeeksGees', 'GeeksGeks', 'GeeksGeks', 'Geekseeks', 'Geek4Geek', 'Geek4Gees', 'Geek4Geks', 'Geek4Geks', 'Geek4eeks', 'GeekGeeks', 'Gees4Geek', 'Gees4Gees', 'Gees4Geks', 'Gees4Geks', 'Gees4eeks', 'GeesGeeks', 'Gee4Geeks', 'Geks4Geek', 'Geks4Gees', 'Geks4Geks', 'Geks4Geks', 'Geks4eeks', 'GeksGeeks', 'Gek4Geeks', 'Ges4Geeks', 'Geks4Geek', 'Geks4Gees', 'Geks4Geks', 'Geks4Geks', 'Geks4eeks', 'GeksGeeks', 'Gek4Geeks', 'Ges4Geeks', 'Gks4Geeks', 'eeks4Geek', 'eeks4Gees', 'eeks4Geks', 'eeks4Geks', 'eeks4eeks', 'eeksGeeks', 'eek4Geeks', 'ees4Geeks', 'eks4Geeks', 'eks4Geeks', 'Geeks4Geek', 'Geeks4Gees', 'Geeks4Geks', 'Geeks4Geks', 'Geeks4eeks', 'GeeksGeeks', 'Geek4Geeks', 'Gees4Geeks', 'Geks4Geeks', 'Geks4Geeks', 'eeks4Geeks']

Time complexity: O(n^2), where n is the length of the input string. The outer loop runs n times, and for each iteration of the outer loop, the slice operation runs in O(n) time. Thus, the overall time complexity is O(n^2).

Space complexity: O(n^2), since the resulting list res will contain n*(n-1)/2 strings, which is O(n^2). The space complexity of the slice operation is O(n), but since it is performed n*(n-1)/2 times, the overall space complexity is O(n^2).