โปรแกรมนับจำนวนสตริงย่อยที่เป็นอักษรเดียวกันใน Python

ปัญหา

ให้สตริง s หาจำนวนสตริงย่อยที่เป็น "homogenous" (ตัวอักษรทุกตัวเหมือนกัน) ผลลัพธ์ modulo 10^9+7

ตัวอย่าง

s = "xyyzzzxx" → ผลลัพธ์ 13 เพราะมี: "x" 3 ครั้ง, "xx" 1 ครั้ง, "y" 2 ครั้ง, "yy" 1 ครั้ง, "z" 3 ครั้ง, "zz" 2 ครั้ง, "zzz" 1 ครั้ง (รวม 3+1+2+1+3+2+1=13)

ขั้นตอนการแก้ปัญหา

1. s := s + "@" (เพื่อจัดการตัวสุดท้าย)
2. h := map ใหม่, prev := s[0], c := 1
3. วนลูป i ใน s[1:]:
   • ถ้า prev != i:
     • อัปเดต h[prev*c] (เพิ่ม 1 หรือตั้งค่า 1)
     • c := 1
   • ถ้า prev == i: c += 1
   • prev := i
4. fin := 0
5. สำหรับแต่ละ key ใน h:
   • t := len(key), k := 0
   • بينما t != 0: k += t; t -= 1
   • fin += k * h[key]
6. คืน fin % 1000000007

การนำไปใช้งาน (Python)

def solve(s):
    s += "@"
    h = {}
    prev = s[0]
    c = 1
    for i in s[1:]:
        if prev != i:
            if prev * c in h:
                h[prev * c] += 1
            else:
                h[prev * c] = 1
            c = 1
        if prev == i:
            c += 1
        prev = i
    fin = 0
    for key in h:
        t = len(key)
        k = 0
        while t != 0:
            k += t
            t -= 1
        fin += k * h[key]
    return fin % 1000000007

s = "xyyzzzxx"
print(solve(s))

อินพุต

"xyyzzzxx"

เอาต์พุต

13