Tìm palindrome dài nhất bằng cách xóa hoặc sắp xếp lại ký tự trong Python

Cho chuỗi, tìm palindrome dài nhất có thể tạo bằng cách xóa hoặc sắp xếp lại các ký tự. Nếu có nhiều palindrome, trả về một trong số chúng.

Ví dụ: "pqqprrs" → "pqrsrqp".

Thuật toán

1. Đếm tần suất mỗi ký tự (mảng size 256).
2. Xây dựng nửa đầu begin: với mỗi ký tự, thêm count//2 lần.
3. Nếu có ký tự lẻ (count & 1), lấy một làm mid (ưu tiên ký tự nhỏ nhất).
4. end = đảo ngược begin.
5. Kết quả = begin + mid + end.

Ví dụ code

def get_palindrome(string):
    count = [0] * 256
    for ch in string:
        count[ord(ch)] += 1
    begin = ""
    mid = ""
    end = ""
    character = ord('a')
    while character <= ord('z'):
        if count[character] & 1:
            mid = chr(character)
            count[character] -= 1
            character -= 1
        else:
            for _ in range(count[character] // 2):
                begin += chr(character)
        character += 1
    end = begin[::-1]
    return begin + mid + end

string = "pqqprrs"
print(get_palindrome(string))

Input

"pqqprrs"

Output

pqrsrqp