没有白走的路,每一步都算数🎈🎈🎈
输入一个字符串,然后计算所有连续子串中没有重复字母的个数
第一行:
一个字符串
所有子串中没有重复字母的个数
样例输入:
ababc
样例输出:
28
理论知识
#子串分值和
import os
import sys
s = input()
count = 0
a = [-1 for i in range(26)]
for i in range(len(s)):
index = ord(s[i])-ord('a')
count+=(len(s)-i)*(i-a[index])
a[index] = i
print(count)
图解文说:
以测试案例ababc为例:
ababc
第一个a的字母的前面没有字母,那么后面的b,ba,bab,babc都能和第一个a链接形成一个新的子串
第一组:b,bc,bcb,bcbc
第二组:ab,aba,abab,ababc
为什么会有两组,因为b的位置在第二个,前面有一个a可以再次拼接
第一组:a,b,c
第二组:ba,bab,babc
为什么会是两组,因为a的位置在第三个,前面有一个b可以再次拼接,但是前面的a不能再次计算,会重复
第一组:b,bc
第二组:ab,abc
上述同理
上述同理
统计可得5+8+6+4+5 =28
现在的这段代码的意思也很明了。
index = ord(s[i])-ord('a')
count+=(len(s)-i)*(i-a[index])
这段代码的第一行的ord是为了得到字母的ASCII码值,然后(len(s)-i)即为默认都会有的长度,会随着字母在字符串中的位置增大而减小,(i-a[index])即表示组数。两者的乘积即为此字母在所有字符子串中出现的个数。
最后累计,就为所输出的值
摘自《《晚熟的人》》:
人类的幸福是建立在痛苦基础上的,美好的事物之所以美好,是因为丑陋事物的存在。