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

Z时代
2024-01-10
分类：综合

假设我们有一个小写的字符串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))