Kiểm tra tần suất ký tự có thể đồng nhất bằng cách xóa 1 ký tự trong Python

Cho chuỗi chữ thường s. Kiểm tra xem có thể xóa một ký tự nào đó để tần suất tất cả các ký tự còn lại bằng nhau hay không.

Ví dụ: "abbc" → xóa một 'b' → "abc" (tần suất 1,1,1) → True.

Thuật toán

1. Đếm tần suất ban đầu. Nếu đã đồng nhất → True.
2. Với mỗi ký tự, giảm tần suất đi 1, kiểm tra đồng nhất. Nếu được → True.
3. Khôi phục và tiếp tục. Cuối cùng → False.

Triển khai

from collections import defaultdict

def all_same(freq):
    vals = list(freq.values())
    return all(v == vals[0] for v in vals)

def solve(s):
    freq = defaultdict(int)
    for ch in s:
        freq[ch] += 1
    if all_same(freq):
        return True
    for ch in s:
        freq[ch] -= 1
        if all_same(freq):
            return True
        freq[ch] += 1
    return False

s = "abbc"
print(solve(s))  # True

Đầu vào / Đầu ra

Input: "abbc"
Output: True

Lưu ý: Độ phức tạp O(n × k) với k = số ký tự distinct (≤26). Có thể tối ưu bằng cách chỉ kiểm tra các tần suất unique.