Chương trình tìm chuỗi nhỏ nhất theo từ điển với giá trị số cho trước trong Python

Cho n (độ dài) và k (giá trị số). Giá trị ký tự: 'a'=1, 'b'=2,... 'z'=26. Giá trị chuỗi = tổng giá trị ký tự. Tìm chuỗi nhỏ nhất theo từ điển độ dài n giá trị k.

Ví dụ: n=4, k=16 → "aaam" (1+1+1+13=16).

Giải thuật (Tham lam từ cuối)

1. Khởi tạo chuỗi rỗng.
2. Trong khi n > 0:
   • letter = min(26, k - n + 1) (để các ký tự còn lại ít nhất là 'a'=1).
   • Nối ký tự tương ứng chr(letter + ord('a') - 1).
   • k -= letter, n -= 1.
3. Đảo ngược chuỗi và trả về.

Ví dụ minh họa

def solve(n, k):
    string = ""
    while n > 0:
        letter = min(26, k - n + 1)
        string += chr(letter + ord('a') - 1)
        k -= letter
        n -= 1
    return string[::-1]

n = 4
k = 16
print(solve(n, k))

Đầu vào

4, 16

Đầu ra

aaam