Kiểm tra 2 nửa chuỗi có cùng tập ký tự (tần suất) trong Python

Bài toán: Cho chuỗi, kiểm tra xem 2 nửa (chia đôi) có chứa cùng các ký tự với tần suất giống hệt nhau không. Nếu độ dài lẻ, bỏ qua ký tự giữa.

Ví dụ

Input: "aabccbaa" (len=8)
Left:  "aabc"  -> a:2, b:1, c:1
Right: "cbaa"  -> a:2, b:1, c:1
Output: Yes!

Thuật toán (Dictionary counting)

1. Tính mid = len // 2.
2. Đếm tần suất ký tự nửa đầu (tăng count).
3. Duyệt nửa sau (giảm count).
4. Kiểm tra tất cả count == 0.

Mã nguồn

string = "aabccbaa"
alphabets = {}
mid = len(string) // 2

# Nửa đầu: tăng count
for i in range(mid):
    ch = string[i]
    alphabets[ch] = alphabets.get(ch, 0) + 1

# Nửa sau: giảm count
for i in range(len(string) - 1, mid - 1, -1):
    ch = string[i]
    if alphabets.get(ch, 0):
        alphabets[ch] -= 1

# Kiểm tra
flag = 1
for count in alphabets.values():
    if count != 0:
        print("No!")
        flag = 0
        break

if flag == 1:
    print("Yes!")

Kết quả

Yes!

Cách ngắn gọn hơn với Counter

from collections import Counter

def halves_same_chars(s):
    mid = len(s) // 2
    first = Counter(s[:mid])
    second = Counter(s[-mid:])  # tự động bỏ ký tự giữa nếu lẻ
    return first == second

print(halves_same_chars("aabccbaa"))  # True
print(halves_same_chars("abcabc"))    # True
print(halves_same_chars("abcabd"))    # False

Kết luận

Cách Counter ngắn gọn, pythonic, hiệu năng tốt. Cách dictionary thủ công giúp hiểu rõ logic counting. Áp dụng cho bài toán anagram, kiểm tra hoán vị.