Kiểm tra tần suất ký tự tạo thành dãy Recaman trong Python

Cho chuỗi chữ thường s. Kiểm tra xem tần suất các ký tự (sắp xếp tùy ý) có khớp với dãy Recaman (bỏ qua số 0 đầu tiên) hay không.

Dãy Recaman: a₀=0; aₙ = aₙ₋₁ - n nếu >0 và chưa xuất hiện, ngược lại aₙ₋₁ + n.

Ví dụ: "pppuvuuqquuu" → tần suất: p(3), u(6), v(1), q(2) → dãy [1,3,6,2] khớp Recaman → True.

Thuật toán

1. Đếm tần suất ký tự → dict freq.
2. Tạo n số đầu của dãy Recaman (n = số ký tự distinct).
3. Kiểm tra mỗi tần suất có nằm trong dãy Recaman không.

Triển khai

from collections import defaultdict

def recaman(arr, n):
    arr[0] = 0
    for i in range(1, n + 1):
        temp = arr[i - 1] - i
        for j in range(i):
            if arr[j] == temp or temp < 0:
                temp = arr[i - 1] + i
                break
        arr[i] = temp

def solve(s):
    freq = defaultdict(int)
    for ch in s:
        freq[ch] += 1
    n = len(freq)
    arr = [0] * (n + 1)
    recaman(arr, n)
    for count in freq.values():
        if count not in arr[1:]:  # bỏ qua arr[0]=0
            return False
    return True

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

Đầu vào / Đầu ra

Input: "pppuvuuqquuu"
Output: True