โปรแกรมหาผลรวมความงามของทุกสตริงย่อยใน 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 + (max(v) - min(v))
• return 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