How to make the below python program more memory efficient for large input

Question

This program is to find the number of substrings with at least i distinct letters where 1<= i <= 26 of a string S of length N.

def DistinctChars (N, S):
    # Write your code here
    substrings = " ".join((S[i:j] for i in range(N) for j in range(i+1, N+1)))
    for i in range(1, 27):
        if i==1:
            yield len(substrings.split(" "))
        else:
            yield len([item for item in substrings.split(" ") if len(set(item)) >= i])
    
 
N = int(input())
S = input()
 
out_ = DistinctChars(N, S)
print (' '.join(map(str, out_)))

example input

N=4

A=aabc

output

10 6 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

The code is fast as needed and the output is correct. But no matter what I tried, it exceeded the allocated memory of 250MB.

Answer 1

I guess the memory limit is being exceeded because all substrings are being stored in one variable. You could instead define a loop to only pre-compute the values of len(set(item)) in your code:

def DistinctChars (N, S):
    
    all_U = []
    for i in range(N):
        D = set()
        for j in range(i, N):
            D.add(S[j])
            all_U.append(len(D))
    
    for i in range(1, 27):
        yield sum( 1 for n in all_U if n>=i)

This approach can save resources exponentially, since all substrings are replaced by only their number of unique characters.

PS. It's actually possible to build an even more efficient algorithm, where the number of substrings with a given number of unique characters is counted immediately. The final answer then corresponds to the cumulative sum of entries with equal or higher number of unique characters:

def DistinctChars (N, S):
    
    all_N = [0]*27
    for i in range(N):
        D = set()
        for j in range(i, N):
            D.add(S[j])
            all_N[len(D)] += 1
    
    result = []
    s      =  0
    for i in range(26,0,-1):
        s += all_N[i]
        result.append(s)
    return reversed(result)