Python程序：求所有子串的美丽值之和

假设我们有一个字符串s。我们需要找到其所有子串的美丽值之和。字符串的美丽值定义为出现频率最高和最低的字符之间的频率差。例如，如果字符串是“abaacc”，则其美丽值为3 - 1 = 2。

因此，如果输入为s = "xxyzy"，则输出将为5，因为美丽值非零的子串为["xxy","xxyz","xxyzy","xyzy","yzy"]，每个子串的美丽值都为1。

为了解决这个问题，我们将遵循以下步骤：

• res := 0

• 对于 i 从 0 到 s 的大小 - 1，执行：

  • 对于 j 从 i+2 到 s 的大小 - 1，执行：

    • c := 一个包含s从索引i到j的子串中字符频率的映射

    • v := c中所有频率值的列表

    • res := res + (v 的最大值 - v 的最小值)

• 返回 res

示例

让我们来看下面的实现，以便更好地理解：

from collections import Counter

def solve(s):
   res=0
   for i in range(len(s)):
      for j in range(i+2,len(s)):
         c=Counter(s[i:j+1])
         v=c.values()
         res+=(max(v)-min(v))
   return res

s = "xxyzy"
print(solve(s))

输入

"xxyzy"

输出

5

Arnab Chakraborty

更新于： 2021年10月6日

627 次浏览

开启你的职业生涯

完成课程获得认证

开始学习