Python Program: จัดเรียง String ให้ตัวอักษรซ้ำห่างกันอย่างน้อย d ระยะ

โจทย์: กำหนด String str (Non-empty) และ Integer k ให้จัดเรียง String ใหม่ ทำให้ตัวอักษรที่เหมือนกันห่างกันอย่างน้อย k ตำแหน่ง หากไม่เป็นไปได้ คืน String ว่าง ""

ตัวอย่าง

อัลกอริทึม (Greedy + Max Heap)

1. นับ Frequency ของแต่ละตัวอักษร
2. สร้าง Max Heap เรียงตาม Frequency มากไปน้อย
3. Extract ตัวอักษรที่ Frequency สูงสุด
4. วางใน Result Array ตำแหน่ง i, i+d, i+2d, ...
5. หากตำแหน่งเกินขนาด Array → ไม่เป็นไปได้
6. ทำซ้ำจนกว่า Heap จะว่าง

Implementation ใน Python

import heapq
from collections import Counter

def rearrange_string(s: str, d: int) -> str:
    if d <= 1:
        return s
    
    n = len(s)
    freq = Counter(s)
    
    # Max Heap: ใช้ negative frequency เพราะ heapq เป็น Min Heap
    max_heap = [(-count, char) for char, count in freq.items()]
    heapq.heapify(max_heap)
    
    result = [''] * n
    
    # ตำแหน่งที่ว่างถัดไปสำหรับแต่ละ Character
    # ใช้ Queue เก็บ (char, remaining_count, next_available_position)
    from collections import deque
    wait_queue = deque()
    
    for i in range(n):
        # ปลดปล่อย Character ที่พร้อมใช้งาน
        if wait_queue and wait_queue[0][2] <= i:
            count, char, _ = wait_queue.popleft()
            heapq.heappush(max_heap, (count, char))
        
        if not max_heap:
            return ""  # ไม่มี Character ให้วาง → Impossible
        
        count, char = heapq.heappop(max_heap)
        result[i] = char
        
        # หากยังเหลือ ใส่ Wait Queue พร้อม Next Available Position
        if count + 1 < 0:  # count เป็น Negative
            wait_queue.append((count + 1, char, i + d))
    
    return ''.join(result)

# ทดสอบ
print(rearrange_string("tutorialspoint", 3))  # tiotiotalnprsu (หรือรูปแบบอื่นที่ถูกต้อง)
print(rearrange_string("aabbcc", 3))          # abcabc
print(rearrange_string("aaabc", 3))           # ""
print(rearrange_string("aaadbbcc", 2))        # abacabcd

การทำงานของอัลกอริทึม (Queue-based)

วิธีนี้ใช้ Max Heap + Wait Queue แทนการคำนวณตำแหน่งแบบ Hard-code:

1. Pop ตัวอักษร Frequency สูงสุดจาก Heap
2. วางในตำแหน่งปัจจุบัน i
3. หากยังเหลือ Count ใส่ Wait Queue พร้อม Next Available = i + d
4. ก่อนรอบใหม่ ตรวจสอบ Wait Queue หาก Character พร้อม (Next Available ≤ i) ใส่กลับ Heap
5. หาก Heap ว่างแต่ยังมีตำแหน่ง → Impossible

Complexity

• Time: O(n log k) โดย k = จำนวน Unique Characters (≤ 26 สำหรับ Lowercase)
• Space: O(n) สำหรับ Result + O(k) สำหรับ Heap/Queue