Chương trình tìm ký tự tại vị trí cho trước trong chuỗi tổng hợp trong Python

Cho chuỗi input_str. Xét tất cả các chuỗi con có thể tạo thành từ chuỗi này, sắp xếp chúng theo thứ tự từ điển (lexicographical), sau đó nối tất cả thành một chuỗi lớn. Cho thêm số nguyên k, hãy tìm ký tự tại chỉ số k (0-based) trong chuỗi nối đó.

Ví dụ: input_str = 'pqrs', k = 6 → kết quả 'p'.

Các chuỗi con theo thứ tự từ điển: p, pq, pqr, pqrs, q, qr, qrs, r, rs, s. Chuỗi nối: ppqpqrpqrsqqrqrsrrss. Vị trí 6 là 'p'.

Thuật toán giải quyết (Duyệt DFS với stack)

1. Khởi tạo stack với tuple ('', list(range(len(input_str))))
2. Khi stack không rỗng:
   • Lấy pre (tiền tố hiện tại) và temp (danh sách chỉ số khả thi)
   • Nếu k < len(pre): trả về pre[k]
   • Cập nhật k -= len(pre)
   • Tạo input_sorted chứa các cặp (ký tự, vị trí) từ temp, sắp xếp giảm dần theo ký tự
   • Duyệt input_sorted, gom nhóm các ký tự giống nhau, đẩy (pre + ký tự, danh_sách_vị_trí_mới) vào stack
3. Trả về None nếu không tìm thấy

Ví dụ minh họa

def solve(input_str, k):
    stk_list = [("", list(range(len(input_str))))]
    while stk_list:
        pre, temp = stk_list.pop()
        if k < len(pre):
            return pre[k]
        k -= len(pre)
        input_sorted = sorted([(input_str[i], i+1) for i in temp if i < len(input_str)], reverse=True)
        i = 0
        while i < len(input_sorted):
            val = input_sorted[i][0]
            temp1 = [input_sorted[i][1]]
            j = i + 1
            while j < len(input_sorted) and input_sorted[j][0] == val:
                temp1.append(input_sorted[j][1])
                j += 1
            stk_list.append((pre + val, temp1))
            i = j
    return None

print(solve('pqrs', 6))

Đầu vào

'pqrs', 6

Đầu ra

p