How can i improve my inefficient solution?

Question

I am a beginner trying to find a way to optimize my inefficient solution to an exercise regarding strings.

The exercise says: Write a function that takes a string of numbers separated by comma, and an integer. The function has to return the number of substrings where the sum of the numbers of each substring is equal to integer passed through the function parameter.

For example: Given the following string and integer

S='3,0,4,0,3,1,0,1,0,1,0,0,5,0,4,2'
m = 9

The function will return 7 because after having generated the substrings, it will count only those in which the sum of the numbers in each substring is equal to 9.

I spent a few hours thinking about a possible solution. I found one that only works in case a short string is given as input. It doesn't work for strings containing hundreds or thousands of numbers.

How can i improve my code so that it can pass the performance tests?

Here you can see my code:

def es(S,m):
    
    string = [int(x) for x in S.split(",")]
    count = 0
    temp_list = []
    for i in range(len(string)):
        for j in range(i,len(string)):
            temp_list.append(string[i:j])
            
    for x in temp_list:
        sumt = sum(x)
        if sumt == m:
            count +=1
    
    return count

I think that if i want my solution to be efficient, i should avoid putting all the substrings of numbers in a new list. I don't know how i could achieve that without using another list.

Any help will be appreciated

This is a classic problem in dynamic programming. Google for "subset sum" — wim, Oct 11 '20 at 23:31
Three hints: 1) You range expression for `j` is wrong. Try printing `temp_list` after you generate it. 2) No need to add sub lists to `temp_list` if they do not add up to `m` and 3) No need to loop through `temp_list` to test sub lists for adding up to `m` if you only add the sublist if the condition is satisfied. Then you only need to return the length of `temp_list` — dawg, Oct 11 '20 at 23:46
[Something like this](https://tio.run/##RZDRCsIgFIav9SkOu0mZjK0VVOBT7HJEDHLlmCbqYD398oxayBH@83/8Ho97x@fL1ifnl@WuelCBNcLwCyV2MgEktNpGNnPoXx5m0BaaIrhRR5aJjF8picq426hDRDZp5DRyvrMPxUZlGSZxjFzN4W/qvBIbkFcrQmaJstWX4YpS9xAmkyaQ0qz@/8Wic07Ze/IIoel4FSdvARM3hlPayF0tSnFIVYsq3b8qxXHt73fUpOnPlDqPv/3ugJNl@QA) That is just editing your code. An 'optimum' solution will either be recursive or dynamic. — dawg, Oct 11 '20 at 23:54
@dawg I googled it, and found that the best solution should be dynamic. Will try it later — alex108, Oct 12 '20 at 00:05
You can look at the dup link too. That is dynamic. If your strings are small, it does not really matter. — dawg, Oct 12 '20 at 00:36

How can i improve my inefficient solution?

0 Answers0