पायथन में संश्लेषित स्ट्रिंग में किसी विशेष इंडेक्स पर अक्षर ढूंढना

मान लीजिए हमें एक स्ट्रिंग 'input_str' दी गई है। अब, हमें दी गई स्ट्रिंग से हर संभव सबस्ट्रिंग निर्धारित करने के लिए कहा गया है, फिर सभी सबस्ट्रिंग्स को लेक्सिकोग्राफिकल ऑर्डर में एक के बाद एक जोड़कर दूसरी स्ट्रिंग बनाना है। हमें एक पूर्णांक मान k भी दिया गया है। हमारा कार्य संयोजित स्ट्रिंग से इंडेक्स k पर अक्षर लौटाना है।

उदाहरण के लिए, यदि इनपुट है input_str = 'pqrs', k = 6, तो आउटपुट होगा p।

दी गई स्ट्रिंग से लेक्सिकोग्राफिकल ऑर्डर में सबस्ट्रिंग्स हैं: p, pq, pqr, pqrs, q, qr, qrs, r, rs, s।

यदि हम स्ट्रिंग्स को जोड़ते हैं, तो यह बन जाता है ppqpqrpqrsqqrqrsrrss। पोजीशन 6 पर अक्षर 'p' है (इंडेक्सिंग 0 से शुरू होती है)।

समाधान दृष्टिकोण

इस समस्या को स्टैक-आधारित डीपथ-फर्स्ट सर्च (DFS) का उपयोग करके हल किया जाता है जो लेक्सिकोग्राफिकल ऑर्डर में सबस्ट्रिंग्स उत्पन्न करता है बिना उन्हें स्पष्ट रूप से संग्रहीत किए।

एक स्टैक को खाली प्रीफिक्स और सभी प्रारंभिक इंडेक्स के साथ आरंभ करें।
जब तक स्टैक खाली नहीं है:
- शीर्ष तत्व (pre, temp) को पॉप करें।
- यदि k < len(pre), तो pre[k] लौटाएं।
- k से len(pre) घटाएं।
- शेष इंडेक्स के आधार पर संभावित अगले अक्षरों को सॉर्ट करें।
- समान अक्षरों को समूहित करें और नए प्रीफिक्स के साथ स्टैक पर पुश करें।
यदि नहीं मिला तो None लौटाएं।

पायथन कार्यान्वयन

def solve(input_str, k):
    stk_list = [("", list(range(len(input_str))))]
    while stk_list:
        pre, temp = stk_list.pop()
        if k < len(pre):
            return pre[k]
        k -= len(pre)
        input_sorted = sorted([(input_str[i], i+1) for i in temp if i < len(input_str)], reverse=True)
        i = 0
        while i < len(input_sorted):
            val = input_sorted[i][0]
            temp1 = [input_sorted[i][1]]
            j = i + 1
            while j < len(input_sorted) and input_sorted[j][0] == val:
                temp1.append(input_sorted[j][1])
                j += 1
            stk_list.append((pre + val, temp1))
            i = j
    return None

print(solve('pqrs', 6))

इनपुट

'pqrs', 6