在Python中计算字符串的每个子字符串的不同字符数的程序

假设我们有一个小写字符串s，我们必须查找s的每个子字符串中都不同的字符计数的总和。如果答案非常大，则返回结果mod 10^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 :=一个新的空映射
ans := 0
定义一个函数util()。这将取i，符号
prev_seen [symbol]：=一个具有单个值-1的列表
prev：= prev_seen [symbol]
将i插入到最后prev
如果prev的大小> 2，则
- left：= prev的第一个元素，并删除prev的第一个元素
- middle：=prev [0]，right：= prev [1]
- cnt：=（middle-left）*（right-middle）
- ans: =（ans + cnt）mod m
对于s中的每个索引i和值符号，执行
- util(i，symbol)
对于prev_seen中的每个符号，执行
- util（s的大小，符号）
return ans

让我们看以下实现以更好地理解 –

更多Python相关文章，请阅读：Python 教程

示例

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