Sắp xếp lại chuỗi sao cho các ký tự giống nhau cách nhau ít nhất k vị trí (Python)

Bài toán: Cho chuỗi str và số nguyên k. Sắp xếp lại chuỗi sao cho các ký tự giống nhau cách nhau ít nhất k vị trí. Trả về chuỗi rỗng nếu không thể.

Ví dụ

• "tutorialspoint", k=3 -> "tiotiotalnprsu"
• "aabbcc", k=3 -> "abcabc"
• "aaabc", k=3 -> "" (không thể)
• "aaadbbcc", k=2 -> "abacabcd" hoặc "abcabcda"

Thuật toán: Max Heap + Greedy

1. Đếm tần suất mỗi ký tự.
2. Xây Max Heap theo tần suất.
3. Lấy ký tự tần suất cao nhất, đặt vào vị trí sớm nhất khả dụng.
4. Đặt các lần xuất hiện tiếp theo cách nhau k vị trí.
5. Nếu vị trí vượt độ dài chuỗi -> không thể sắp xếp.

Code Python

MAX_CHAR = 128  # ASCII

class CharFreq:
    def __init__(self, char, freq):
        self.c = char
        self.f = freq

def max_heapify(freq, i, heap_size):
    l = 2 * i + 1
    r = 2 * i + 2
    largest = i
    if l < heap_size and freq[l].f > freq[largest].f:
        largest = l
    if r < heap_size and freq[r].f > freq[largest].f:
        largest = r
    if largest != i:
        freq[i], freq[largest] = freq[largest], freq[i]
        max_heapify(freq, largest, heap_size)

def build_heap(freq, n):
    i = (n - 1) // 2
    while i >= 0:
        max_heapify(freq, i, n)
        i -= 1

def extract_max(freq, heap_size):
    root = freq[0]
    if heap_size > 1:
        freq[0] = freq[heap_size - 1]
        max_heapify(freq, 0, heap_size - 1)
    return root

def rearrange(string, d):
    n = len(string)
    freq = [CharFreq(0, 0) for _ in range(MAX_CHAR)]
    m = 0
    
    # Đếm tần suất
    for ch in string:
        idx = ord(ch)
        if freq[idx].c == 0:
            freq[idx].c = ch
            m += 1
        freq[idx].f += 1
    
    # Build max heap
    build_heap(freq, MAX_CHAR)
    
    # Mảng kết quả
    result = ['\0'] * n
    
    # Trích xuất và đặt
    for i in range(m):
        x = extract_max(freq, MAX_CHAR - i)
        
        # Tìm vị trí trống đầu tiên
        p = i
        while p < n and result[p] != '\0':
            p += 1
        
        # Đặt x.c tại p, p+d, p+2d, ...
        for k in range(x.f):
            pos = p + d * k
            if pos >= n:
                return ""  # Không thể sắp xếp
            result[pos] = x.c
    
    return ''.join(result)

# Test
print(rearrange("tutorialspoint", 3))  # tiotiotalnprsu
print(rearrange("aabbcc", 3))          # abcabc
print(rearrange("aaabc", 3))           # (empty)
print(rearrange("aaadbbcc", 2))        # abacabcd

Phiên bản đơn giản hơn (Pythonic, dùng heapq)

import heapq
from collections import Counter

def rearrange_simple(s, k):
    if k <= 1:
        return s
    
    count = Counter(s)
    max_heap = [(-freq, char) for char, freq in count.items()]
    heapq.heapify(max_heap)
    
    result = []
    wait_queue = []  # (available_index, freq, char)
    
    for i in range(len(s)):
        # Giải phóng char đã hết cooldown
        if wait_queue and wait_queue[0][0] == i:
            _, freq, char = heapq.heappop(wait_queue)
            heapq.heappush(max_heap, (freq, char))
        
        if not max_heap:
            return ""
        
        freq, char = heapq.heappop(max_heap)
        result.append(char)
        
        # Nếu còn lần xuất hiện, cho vào wait queue
        if freq + 1 < 0:  # freq là âm
            heapq.heappush(wait_queue, (i + k, freq + 1, char))
    
    return ''.join(result)

print(rearrange_simple("tutorialspoint", 3))
print(rearrange_simple("aabbcc", 3))
print(rearrange_simple("aaabc", 3))
print(rearrange_simple("aaadbbcc", 2))

Độ phức tạp

• Thời gian: O(n log σ) (σ = số ký tự khác nhau, ≤ 128 ASCII).
• Không gian: O(σ).