Tìm người chơi sắp xếp chuỗi thành palindrome trước trong Python

Cho chuỗi S chữ thường. Hai người chơi chơi game theo quy tắc:

• Người chơi thắng nếu tại lượt của mình, họ có thể sắp xếp lại các ký tự của chuỗi thành một chuỗi palindrome.
• Người chơi không thể thắng khi phải xóa ký tự khỏi chuỗi.

Cả hai chơi tối ưu, người chơi 1 đi trước. Xác định người thắng.

Ví dụ, "pqpppq" -> Người chơi 1 thắng vì có thể sắp thành "ppqqpp".

Thuật toán giải quyết

• Đếm tần suất từng ký tự.
• Đếm số ký tự xuất hiện số lẻ lần (count).
• Nếu count == 0 hoặc count lẻ: Người chơi 1 thắng.
• Ngược lại: Người chơi 2 thắng.

Ví dụ minh họa

def who_is_the_winner(sequence):
    l = len(sequence)
    freq = [0] * 26
    for i in range(l):
        freq[ord(sequence[i]) - ord('a')] += 1
    count = 0
    for i in range(26):
        if freq[i] % 2 != 0:
            count += 1
    if count == 0 or count & 1 == 1:
        return 1
    else:
        return 2

sequence = "pqpppq"
print("Player:", who_is_the_winner(sequence))  # Player: 1

Đầu vào

"pqpppq"

Đầu ra

Player: 1