1. Python
  2. Python | Find all possible substrings after removing k characters

Python | Find all possible substrings after removing k characters



Examples :

  Input:  geeks, k = 1  Output:  {`gees`,` eeks` , `geks`,` geek`}  Input:  dog, k = 1  Output:  {`do`,` dg`, `og`}

Approach # 1: Naive Approach
This is a recursive naive approach to find all possible substrings after k characters have been removed. First, we initialize the start, end and index variable with 0, string length and 0 respectively. We create a temporary list, say “ temp “, which stores all the output one by one. We start at the first index in temp [] , commit items one by one at that index, and repeat for the rest of the indexes.

# Python3 program for finding all combinations
Number of lines after removing k characters

list = []

 

def findCombinations ( str , temp, start, end, index, k): 

 

if (index = = k): 

  item = ` `

 

for j in range (k ): 

item + = temp [j]

  list . append (item)

  return ; 

 

i = start; 

while (i & lt; = end and end - i + 1 & gt; = k - index): 

temp [index] = str [i]

findCombinations ( str , temp, i + 1 , 

  end, index + 1 , k); 

i + = 1 ; 

 
Driver code

str = `geeks`

k = 1

temp = [ 0 ] * ( len ( str ) - k)

s, e = 0 , len ( str ) - 1

  

findCombinations ( str , temp, s, e, 0 , len ( str ) - k)

print ( set ( list ))

Exit: 

 {`eeks`,` gees`, `geks`,` geek`}

Approach # 2 Using Itertools
The Python Itertools module provides a combination () function that takes a string and a length to get all possible string combinations.

# Python3 program to find all combinations
Number of lines after removing k characters

from itertools import combinations

 

def findCombinations ( str , k):

  l = len ( str )

return set ([`` .join (i) for i in combinations ( str , l - k)])

 
Driver code

str = `geeks`

k = 1

print (findCombinations ( str , k))

Exit :

 {`geek`,` eeks`, `geks`,` gees`}