Tìm chuỗi nhỏ nhất theo thứ tự từ điển thỏa mãn điều kiện tiền tố trong Python

Cho mảng A[n], A[i] là số ký tự khác nhau trong tiền tố độ dài i+1 của chuỗi s. Tìm chuỗi s nhỏ nhất theo thứ tự từ điển thỏa mãn (chữ cái thường a-z). Nếu không tồn tại, trả về -1.

Ví dụ: A = [1,1,2,3,4] → "aabcd" (tiền tố 1 ký tự: 1 khác biệt, tiền tố 2: 1, tiền tố 3: 2...).

Giải thuật

• Kiểm tra A[0] == 1, nếu không → -1.
• Khởi tạo chuỗi kết quả = "a", ký tự tiếp theo = 'b'.
• Duyệt i từ 1 đến n-1:
  • diff = A[i] - A[i-1].
  • Nếu diff > 1 hoặc diff < 0 hoặc A[i] > 26 → -1.
  • Nếu diff == 0 → thêm 'a' vào kết quả.
  • Nếu diff == 1 → thêm ký tự tiếp theo, tăng ký tự tiếp theo.

Ví dụ

def get_smallest_string(A):
    n = len(A)
    character = 'a'
    string = ""
    if n < 1 or A[0] != 1:
        return -1
    string += character
    character = chr(ord(character) + 1)
    for i in range(1, n):
        diff = A[i] - A[i - 1]
        if diff > 1 or diff < 0 or A[i] > 26:
            return -1
        elif diff == 0:
            string += 'a'
        else:
            string += character
            character = chr(ord(character) + 1)
    return string

A = [1, 1, 2, 3, 4]
print(get_smallest_string(A))

Đầu vào

[1, 1, 2, 3, 4]

Đầu ra

aabcd