 # 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`} `