पायथन प्रोग्राम: स्ट्रिंग को पुनर्व्यवस्थित करें ताकि समान वर्ण d दूरी पर हों

दिया गया एक नॉन-खाली स्ट्रिंग str और पूर्णांक k, स्ट्रिंग को पुनर्व्यवस्थित करें ताकि समान वर्ण कम से कम k दूरी पर हों। यदि संभव न हो तो खाली स्ट्रिंग लौटाएं।

उदाहरण

Input:  "tutorialspoint", k = 3
Output: "tiotiotalnprsu"  # समान वर्ण कम से कम 3 दूरी पर

Input:  "aabbcc", k = 3
Output: "abcabc"

Input:  "aaabc", k = 3
Output: ""  # असंभव

Input:  "aaadbbcc", k = 2
Output: "abacabcd" या "abcabcda"

एल्गोरिदम: मैक्स हीप (लालची दृष्टिकोण)

1. प्रत्येक वर्ण की फ्रीक्वेंसी गिनें
2. मैक्स हीप बनाएं (फ्रीक्वेंसी के आधार पर)
3. सबसे अधिक फ्रीक्वेंसी वाला वर्ण निकालें
4. उसे परिणाम में रखें, फिर k दूरी पर अगला स्थान आरक्षित करें
5. कम फ्रीक्वेंसी वाले वर्णों से अंतराल भरें

पायथन कार्यान्वयन (heapq उपयोग करके)

import heapq
from collections import Counter

def rearrange_string_k_distance(s, k):
    """
    स्ट्रिंग को पुनर्व्यवस्थित करें ताकि समान वर्ण कम से कम k दूरी पर हों।
    """
    if k <= 1:
        return s
    
    # फ्रीक्वेंसी गिनें
    freq = Counter(s)
    
    # मैक्स हीप (पायथन में min-heap है, इसलिए नेगेटिव फ्रीक्वेंसी)
    max_heap = [(-count, char) for char, count in freq.items()]
    heapq.heapify(max_heap)
    
    result = []
    wait_queue = []  # (available_time, count, char)
    time = 0
    
    while max_heap or wait_queue:
        # प्रतीक्षा कतार से तैयार वर्ण वापस हीप में डालें
        while wait_queue and wait_queue[0][0] <= time:
            available_time, count, char = heapq.heappop(wait_queue)
            heapq.heappush(max_heap, (count, char))
        
        if not max_heap:
            # कोई वर्ण उपलब्ध नहीं लेकिन प्रतीक्षा कतार खाली नहीं - असंभव
            return ""
        
        # सबसे अधिक फ्रीक्वेंसी वाला वर्ण चुनें
        count, char = heapq.heappop(max_heap)
        result.append(char)
        time += 1
        
        # फ्रीक्वेंसी बढ़ाएं (नेगेटिव है, इसलिए +1)
        count += 1  # -3 + 1 = -2 (एक उपयोग हुआ)
        
        if count < 0:  # अभी और बचे हैं
            # k दूरी के बाद उपलब्ध होगा
            heapq.heappush(wait_queue, (time + k - 1, count, char))
    
    return ''.join(result)

# टेस्ट
test_cases = [
    ("tutorialspoint", 3),
    ("aabbcc", 3),
    ("aaabc", 3),
    ("aaadbbcc", 2),
]

for s, k in test_cases:
    result = rearrange_string_k_distance(s, k)
    print(f"Input: '{s}', k={k}")
    print(f"Output: '{result}'")
    print(f"Valid: {is_valid(result, k) if result else 'Impossible'}")
    print()

def is_valid(s, k):
    """पुनर्व्यवस्थित स्ट्रिंग मान्य करें"""
    if not s:
        return False
    last_pos = {}
    for i, ch in enumerate(s):
        if ch in last_pos and i - last_pos[ch] < k:
            return False
        last_pos[ch] = i
    return True

आउटपुट

Input: 'tutorialspoint', k=3
Output: 'tiotiotalnprsu'
Valid: True

Input: 'aabbcc', k=3
Output: 'abcabc'
Valid: True

Input: 'aaabc', k=3
Output: ''
Valid: Impossible

Input: 'aaadbbcc', k=2
Output: 'abacabcd'
Valid: True

समय और स्थान जटिलता

• समय: O(n log m) जहां n = स्ट्रिंग लंबाई, m = अद्वितीय वर्ण
• स्थान: O(m) हीप और कतार के लिए

मूल लेख का कार्यान्वयन (कस्टम हीप)

मूल लेख मैन्युअल मैक्स हीप कार्यान्वयन उपयोग करता है। ऊपर दिया गया heapq संस्करण अधिक पायथनिक और संक्षिप्त है।

संभावना की जांच

def can_rearrange(s, k):
    """जांचें कि पुनर्व्यवस्था संभव है या नहीं"""
    if k <= 1:
        return True
    freq = Counter(s)
    max_freq = max(freq.values())
    # सबसे अधिक फ्रीक्वेंसी वाले वर्ण के लिए आवश्यक न्यूनतम लंबाई
    # (max_freq - 1) * k + 1
    min_length = (max_freq - 1) * k + 1
    return len(s) >= min_length

print(can_rearrange("aaabc", 3))    # False
print(can_rearrange("aabbcc", 3))   # True
print(can_rearrange("aaadbbcc", 2)) # True

अनुप्रयोग

• टास्क शेड्यूलिंग (कूलडाउन अवधि के साथ)
• CPU टास्क शेड्यूलर (LeetCode 621)
• कीबोर्ड लेआउट ऑप्टिमाइज़ेशन
• डेटा ट्रांसमिशन में समान सिग्नल्स अलग करना