count substrings of a string with limitation

user_14310125 0
Viewed 70

I have a string and a dictionary. I need to count number of substrings of a given string that has letters(and number of letters) not more than in the dict. I counted only 15 substrings(2a +4b +1d + 2ba + 2ab +bd +db +abc +dba) but I cannot write the program. Need to upgrade it(I hope it requires only ELSE condition)

string = 'babdbabcce'
dict= {'a':1,'b':1,'d':1}
counter= 0
answer = 0

for i in range(len(string)):
    for j in dict:
        if string[i] == j:
            if dict[j] > 0:
                dict[j] = dict[j] - 1
                counter+= 1
                answer+= counter
#             else:                  
print(answer)
substring python string
1 Answers

It seems like you're looking for permutations of strings (including substrings within them) within another string, so build the strings using the dictionary, then load the permutations, then count the permutations in the other string. Note that this probably not the most efficient solution, but it's effective.

Example code:

import itertools
import re

string_to_look_into = 'babdbabcce'
dict= {'a':1,'b':1,'d':1}

permutation_string = ''
for c, n in dict.items():
    permutation_string += c * n


permutations = itertools.permutations(permutation_string)
matches_to_count = set()
for perm in permutations:
    for i in range(1, len(perm)+1):
        matches_to_count.add(''.join(perm[:i]))


sum_dict = {} # to verify matches
sum = 0
for item in matches_to_count:
    count = len(re.findall(item, string_to_look_into))
    sum_dict[item] = count
    sum += count


print(sum)
user_66423070
Related