Chương trình kiểm tra hai chuỗi có thể bằng nhau bằng hoán đổi ký tự Python

Cho hai chuỗi chữ thường s và t cùng độ dài. Có thể chọn một ký tự từ s và một từ t hoán đổi cho nhau, lặp lại bao nhiêu lần tùy ý. Kiểm tra có thể làm cho hai chuỗi giống nhau không.

Ví dụ: s="abcd", t="cdab" → True.

Giải thuật (Đếm tần suất ký tự)

1. Đếm tần suất ký tự trong chuỗi nối s + t
2. Nếu mọi ký tự xuất hiện chẵn lần → có thể hoán đổi để bằng nhau (True)
3. Nếu có ký tự xuất hiện lẻ lần → không thể (False)

Lý do: hoán đổi giữa s và t bảo toàn tổng số lượng mỗi ký tự. Để s=t, mỗi ký tự phải xuất hiện chẵn lần trong tổng.

Ví dụ triển khai

from collections import Counter

def solve(s, t):
    fre = Counter(s + t)
    for cnt in fre.values():
        if cnt % 2:
            return False
    return True

print(solve("abcd", "cdab"))

Đầu vào

"abcd", "cdab"

Đầu ra

True