程序可计算Python中字符串的每个子字符串的不同字符数
假设我们有一个小写的字符串s，我们必须找到s的每个子字符串中不同的字符数的总和。如果答案很大，则返回结果mod10^9+7。
因此，如果输入类似于s=“xxy”，则输出将为6，因为子字符串及其计数为-
“x”：1
“x”：1
“y”：1
“xx”：0（因为“x”没有区别）
“xy”：2
“xxy”：1（“因为”x“不区分）
为了解决这个问题，我们将遵循以下步骤-
m：=10^9+7
prev_seen：=一个新的空映射
回答：=0
定义一个功能util()。这将带我，符号
prev_seen[symbol]：=具有单个值-1的列表
上一个：=prev_seen[symbol]
在上一个结尾处插入i
如果prev的大小>2，则
left：=prev的第一个元素，并从prev中删除第一个元素
中：=上一个[0]，右：=上一个[1]
cnt：=（中间-左）*（右边-中间）
ans：=（ans+cnt）modm
对于s中的每个索引i和值符号，执行
util(i,symbol)
对于prev_seen中的每个符号，执行
util(sizeofs,symbol)
返回ans
让我们看下面的实现以更好地理解-
示例
class Solution:
def solve(self, s):
m = 10 ** 9 + 7
prev_seen = {}
ans = 0
def util(i, symbol):
nonlocal ans
prev = prev_seen.setdefault(symbol, [−1])
prev.append(i)
if len(prev) > 2:
left = prev.pop(0)
middle, right = prev
cnt = (middle − left) * (right − middle)
ans = (ans + cnt) % m
for i, symbol in enumerate(s):
util(i, symbol)
for symbol in prev_seen:
util(len(s), symbol)
return ans
ob = Solution()
s = "xxy"
print(ob.solve(s))输入值
xxy输出结果
6