পাইথনে সমস্ত সম্ভাব্য সাবস্ট্রিংকে লেক্সিক্যাল অর্ডারে জোড়া দিয়ে নির্দিষ্ট সূচকের অক্ষর বের করার প্রোগ্রাম

একটি স্ট্রিং input_str এবং একটি ইন্টিজার k দেওয়া আছে। স্ট্রিং-এর সব সম্ভাব্য সাবস্ট্রিং বের করে লেক্সিক্যাল অর্ডারে সাজিয়ে একসাথে জোড়া দিন। তারপর কনক্যাটেনেটেড স্ট্রিং-এর k-তম সূচকের অক্ষর রিটার্ন করুন (০-ভিত্তিক ইন্ডেক্সিং)।

উদাহরণ

input_str = 'pqrs', k = 6 → আউটপুট: 'p'

লেক্সিক্যাল অর্ডারে সাবস্ট্রিং: p, pq, pqr, pqrs, q, qr, qrs, r, rs, s

কনক্যাটেনেটেড: ppqpqrpqrsqqrqrsrrss → সূচক ৬-এ 'p'

এলগরিদম (স্ট্যাক-ভিত্তিক DFS)

1. stk_list := [("", list(range(len(input_str))))]
2. while stk_list:
   • pre, temp := stk_list.pop()
   • যদি 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; একই val वालা সব এন্ট্রি temp1-এ জমান।
     • stk_list.append((pre+val, temp1)), i := j
3. 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))  # আউটপুট: p

ইনপুট / আউটপুট

'pqrs', 6
p