Kiểm tra có thể sắp xếp lại chuỗi thành palindrome trong Python

Cho chuỗi s. Kiểm tra xem có thể sắp xếp lại các ký tự của s thành một palindrome hay không.

Điều kiện: tối đa một ký tự có tần suất lẻ (đối với chuỗi độ dài lẻ), hoặc không ký tự nào lẻ (độ dài chẵn).

Ví dụ: "raaecrc" → sắp xếp thành "racecar" → True.

Giải thuật

• Đếm tần suất ký tự.
• Đếm số ký tự có tần suất lẻ (odd_count).
• Nếu odd_count > 1 → False, ngược lại True.

Mã ví dụ

from collections import defaultdict

def solve(st):
    freq = defaultdict(int)
    for char in st:
        freq[char] += 1
    odd_count = 0
    for cnt in freq.values():
        if cnt % 2 == 1:
            odd_count += 1
        if odd_count > 1:
            return False
    return True

s = "raaecrc"
print(solve(s))

Đầu vào

"raaecrc"

Đầu ra

True