Given a string and an Integer k, write a Python program to find all possible substrings of the given string after deleting k characters. Examples:
Input :neveropen, k = 1
Output : {'gees', 'eeks', 'geks', 'geek'}
Input : dog, k = 1
Output : {'do', 'dg', 'og'}
Approach #1 : Naive Approach This is the recursive naive approach to find all possible substrings after deleting k characters. First, we initialize start, end and index variable with 0, length of string and 0 respectively. We create a temporary list, say ‘temp‘ which stores all outputs one by one. We start from first index in temp[], one by one fix elements at this index and recur for remaining indexes.
Python3
# Python3 program to Find all combinations # of string after deleting k characterslist = []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 <= end and end - i + 1 >= k - index): temp[index] = str[i] findCombinations(str, temp, i + 1, end, index + 1, k); i += 1; # Driver Codestr = 'neveropen'k = 1temp = [0]*(len(str)-k)s, e = 0, len(str)-1findCombinations(str, temp, s, e, 0, len(str)-k)print(set(list)) |
{'eeks', 'gees', 'geks', 'geek'}
Approach #2 : Using Itertools The Python module Itertools gives a function combination(), which takes the string and length to give all possible combinations of a string.
Python3
# Python3 program to Find all combinations # of string after deleting k charactersfrom itertools import combinationsdef findCombinations(str, k): l = len(str) return set([''.join(i) for i in combinations(str, l - k)]) # Driver Codestr = 'neveropen'k = 1print(findCombinations(str, k)) |
{'geek', 'eeks', 'geks', 'gees'}
Method#3: using recursion + conditional statements
Approach
The approach is an implementation of a function get_substrings that takes a string s and an integer k as input, and returns a set containing all possible substrings that can be obtained by deleting k characters from the original string s.
Algorithm
1. Initialize a set substrings to store all possible substrings.
2. For each combination of k characters to be deleted from the original string:
a. Delete the k characters specified in the combination.
b. Add the resulting substring to the substrings set if its length is at least equal to the length of the original string minus k.
3. Return the substrings set.
Python3
from itertools import combinationsdef get_substrings(s, k): n = len(s) substrings = set() for comb in combinations(range(n), k): temp = "" for i in range(n): if i not in comb: temp += s[i] if len(temp) >= n - k and temp not in substrings: substrings.add(temp) return substringss = 'neveropen'k = 1print(get_substrings(s, k)) |
{'eeks', 'gees', 'geek', 'geks'}
Time complexity: O(n choose k * n), where n is the length of the input string s. This is because we are generating all possible combinations of k characters to be deleted from the original string, which can be done in O(n choose k) time using the combinations function from the itertools module. For each combination, we are constructing a new substring of length n-k by excluding the characters specified in the combination, which takes O(n) time.
Auxiliary Space: O(n choose k * (n-k)), which is the maximum possible size of the substrings set. This occurs when all possible substrings of length n-k are generated, which is O(n choose k). Each of these substrings can have a maximum length of n-k, so the maximum size of the substrings set is O(n choose k * (n-k)).
METHOD 4:Using counter method
APPROACH:
Given a string s and an integer k, the task is to find all possible substrings of s that can be obtained by deleting k characters from s.
ALGORITHM:
1.Initialize a Counter object to count the frequency of each character in the input string s.
2.Define a recursive function backtrack that takes two arguments: start (the starting index of the current substring being constructed) and curr (the current substring being constructed).
3.In the backtrack function, if the length of the current substring curr is equal to n-k, where n is the length of s, then add curr to a set of candidate substrings.
4.Otherwise, iterate through the characters in s starting from index start. If the frequency of the current character is greater than 0, then append the current character to curr, decrement its frequency in the Counter object, and recursively call backtrack with the updated start and curr.
5.After the recursive call returns, restore the frequency of the current character in the Counter object to its original value.
6.Return the set of candidate substrings
Python3
from collections import Counterdef get_possible_substrings(s, k): n = len(s) freq = Counter(s) candidates = set() def backtrack(start, curr): if len(curr) == n - k: candidates.add(curr) return for i in range(start, n): char = s[i] if freq[char] > 0: freq[char] -= 1 backtrack(i+1, curr+char) freq[char] += 1 backtrack(0, '') return candidates# Example usages = 'neveropen'k = 1substrings = get_possible_substrings(s, k)print(substrings) # Output: {'geks', 'eeks', 'gees', 'geek'} |
{'gees', 'eeks', 'geks', 'geek'}
Time Complexity:
The time complexity of this solution is O(2^n), where n is the length of the input string. This is because in the worst case, we need to consider all possible substrings of the input string, which is 2^n.
Space Complexity:
The space complexity of this solution is also O(2^n), since we need to store all possible substrings of the input string in the set of candidate substrings. However, in practice, the actual number of candidate substrings is likely to be much smaller than 2^n.
