Python - Chuỗi chữ thường nhỏ nhất theo từ điển độ dài k và tổng giá trị n

Cho n (tổng giá trị) và k (độ dài). Tìm chuỗi chữ thường nhỏ nhất theo thứ tự từ điển độ dài k có tổng giá trị chữ cái = n (a=1, b=2, ..., z=26).

Ví dụ

Input: n = 15, k = 3
Output: "aam"
Giải thích: a(1) + a(1) + m(13) = 15. "aam" < "aba" < "abb"...

Thuật toán: Tham lam từ phải sang trái

1. Khởi tạo mảng dist độ dài k toàn giá trị 1 (tức 'a')
2. credit = n - k (điểm còn lại để phân phối)
3. Duyệt từ phải sang trái (i = k-1 xuống 0):
   • Thêm vào dist[i] giá trị min(credit, 25) (tối đa 'z' = 26)
   • Trừ credit
4. Chuyển dist thành chuỗi: chr(d - 1 + ord('a'))

Mã Python

def solve(n, k):
    dist = [1] * k        # Mặc định toàn 'a' (giá trị 1)
    credit = n - k        # Điểm dư cần phân bổ
    i = k - 1             # Bắt đầu từ cuối (ít quan trọng nhất cho thứ tự từ điển)
    
    while credit > 0:
        val = min(credit, 25)  # Tối đa cộng 25 để thành 'z'
        dist[i] += val
        credit -= val
        i -= 1
    
    return "".join(chr(d - 1 + ord("a")) for d in dist)

# Test
n, k = 15, 3
print(solve(n, k))  # Output: aam

Tại sao tham lam từ phải sang trái?

Để chuỗi nhỏ nhất theo từ điển, ta muốn các ký tự bên trái càng nhỏ càng tốt. Do đó, ta đẩy toàn bộ "điểm dư" sang bên phải nhất có thể.

Phân tích độ phức tạp

• Thời gian: O(k)
• Không gian: O(k)

Điều kiện hợp lệ: k ≤ n ≤ 26*k. Nếu không thỏa mãn, không tồn tại chuỗi thỏa mãn.