程序可计算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：=一个新的空映射

• 回答：= 0

• 定义一个功能util()。这将带我，符号

• prev_seen [symbol]：=具有单个值-1的列表

• 上一个：= prev_seen [symbol]

• 在上一个结尾处插入i

• 如果prev的大小> 2，则

• left：= prev的第一个元素，并从prev中删除第一个元素

• 中：=上一个[0]，右：=上一个[1]

• cnt：=（中间-左）*（右边-中间）

• ans：=（ans + cnt）mod m

• 对于s中的每个索引i和值符号，执行

• util(i, symbol)

• 对于prev_seen中的每个符号，执行

• util(size of s , 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