程序可计算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