โปรแกรมหาจำนวน Operation น้อยที่สุดเพื่อเรียงสตริงใน Python

ปัญหา

กำหนดสตริง s ทำ Operation ซ้ำจนเรียงลำดับ: 1. หา i สุดท้ายที่ s[i] < s[i-1] 2. หา j สุดท้ายที่ s[k] < s[i-1] สำหรับทุก k ใน [i, j] 3. สลับ s[i-1] และ s[j] 4. Reverse suffix ตั้งแต่ i หาจำนวน Operations (Mod 10^9+7)

ตัวอย่าง

s = "ppqpp" → 2 Operations

1: i=3, j=4 → swap s[2],s[4] → "ppppq" → reverse from 3 → "pppqp"

2: i=4, j=4 → swap s[3],s[4] → "ppppq" → reverse from 4 → "ppppq" (Sorted)

อัลกอริทึม (Next Permutation Ranking)

การดำเนินการนี้คือการหา Next Permutation แบบ Lexicographic จำนวน Operations = Rank ของ Permutation ปัจจุบัน (0-indexed) ในลำดับ Permutation ทั้งหมดที่เรียงแล้ว

ใช้สูตร Factorial Number System (Lehmer Code) คำนวณ Rank แบบ Modulo

ตัวอย่างโค้ด

def solve(s):
    d = [0] * 26
    a = 0
    t = 1
    m = 10**9 + 7
    n = ord('a')
    
    for i, c in enumerate(s[::-1], 1):
        j = ord(c) - n
        d[j] += 1
        a = (a + sum(d[:j]) * t // d[j]) % m
        t = t * i // d[j]
    return a

s = "ppqpp"
print(solve(s))  # 2

ความซับซ้อน

• Time: O(n × 26) ≈ O(n)
• Space: O(26) = O(1)