如何使下面的python程序在大输入时具有更高的内存效率

Question

此程序用于查找至少有i个不同字母的子字符串的数量，其中1<=i<=长度为N的字符串S的26。

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_)))

示例输入

N=4

A=aabc

输出

10 6 1 0 0 0 0

代码根据需要快速，并且输出正确。但无论我尝试什么，它都超过了250MB的分配内存。

Answer 1

我想内存限制被超过了，因为所有substrings都存储在一个变量中。相反，您可以定义一个循环，只预先计算代码中len(set(item))的值：

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)

这种方法可以成倍地节省资源，因为所有子字符串都只替换为其数量的唯一字符。

PS。实际上，可以构建一种更高效的算法，即立即计算具有给定数量的唯一字符的子字符串的数量。最终答案对应于具有相同或更高数量的唯一字符的条目的累积总和：

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)