Chương trình tìm tổng độ đẹp của tất cả chuỗi con trong Python

Cho chuỗi s. Tìm tổng độ đẹp (beauty) của tất cả chuỗi con. Độ đẹp = tần suất ký tự nhiều nhất - tần suất ký tự ít nhất. Ví dụ "abaacc": tần suất a=3, b=1, c=2, độ đẹp = 3-1=2.

Ví dụ: s = "xxyzy", đầu ra = 5 (5 chuỗi con có độ đẹp 1: "xxy", "xxyz", "xxyzy", "xyzy", "yzy").

Giải pháp

Duyệt tất cả chuỗi con độ dài ≥ 3, đếm tần suất, tính độ đẹp:

• res := 0
• Với i từ 0 đến len(s)-1:
  • Với j từ i+2 đến len(s)-1:
    • c := Counter(s[i:j+1])
    • v := list(c.values())
    • res += max(v) - min(v)
• Trả về res

Ví dụ minh họa

Xem triển khai sau để hiểu rõ hơn:

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

Đầu vào

"xxyzy"

Đầu ra

5