Python:如何优化

Question

假设给我一个字符串 len n，对于第一个和最后一个字符相同的每个子字符串，我应该将 1 添加到 fx并打印最终的 fx 。

例如 "ababaca" , f("a")=1 , f("aba")=1 , f("abaca")=1 ，但是f("ab")=0

n = int(raw_input())
string = list(raw_input())
f = 0
for i in range(n):
    for j in range(n,i,-1):
        temp = string[i:j]
        if temp[0]==temp[-1]:
            f+=1
print f

有什么方法可以优化大字符串的代码，因为我在许多测试用例中都超时了。

Answer 1

您可以只计算每个字母的出现次数。例如，如果有n个“a”，则字符串中将有n*(n-1)/2个以“a”开头和结尾的子字符串。您可以对每个字母执行相同的操作，解决方案是线性的。

将 len(string) 添加到获得的值中以获得最终答案。