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"

輸出

Arnab Chakraborty

更新於： 2021年10月6日

627 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習