ধরুন, আমাদের একটি স্ট্রিং 'input_str' দেওয়া হয়েছে। এখন, আমাদেরকে প্রদত্ত স্ট্রিং থেকে প্রতিটি সম্ভাব্য সাবস্ট্রিং নির্ধারণ করতে বলা হয়েছে এবং তারপরে সমস্ত সাবস্ট্রিংগুলিকে আভিধানিক ক্রমে অন্য স্ট্রিংয়ে একের পর এক সংযুক্ত করতে বলা হয়েছে। আমাদের একটি পূর্ণসংখ্যা মান k প্রদান করা হয়। আমাদের কাজ হল সংযোজিত স্ট্রিং থেকে সূচক k-তে অক্ষরটি ফেরত দেওয়া।
সুতরাং, যদি ইনপুটটি হয় input_str ='pqrs', k =6, তাহলে আউটপুট হবে p
আভিধানিক ক্রমে প্রদত্ত স্ট্রিং থেকে সাবস্ট্রিংগুলি হল p, pq, pqr, pqrs, q, qr, qrs, r, rs, s৷
যদি আমরা স্ট্রিংগুলিকে সংযুক্ত করি তবে এটি ppqpqrpqrsqqrqrsrrss হয়ে যায়। 6 অবস্থানে, অক্ষরটি 'p'। (সূচীকরণ 0 এ শুরু হয়)।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- stk_list :=একটি নতুন তালিকা যেখানে একটি টিপল রয়েছে যাতে একটি ফাঁকা স্ট্রিং এবং input_str থেকে সমস্ত অক্ষরগুলির একটি তালিকা রয়েছে
- যদিও stk_list খালি না, কর
- pre :=stk_list থেকে শেষ উপাদান মুছে দিন
- temp :=stk_list থেকে শেষ উপাদান মুছুন
- যদি k
- প্রত্যাবর্তনের পূর্বে[k]
- k :=k - পূর্বের আকার
- input_sorted :=একটি নতুন তালিকা যাতে tuples রয়েছে যাতে input_str এর অক্ষর থাকে এবং input_str এ তাদের অবস্থান
- একটি অবতরণ ক্রমে tuples দ্বিতীয় মানের উপর ভিত্তি করে ইনপুট_sorted তালিকা সাজান
- i :=0
- যখন আমি
- val :=input_sorted[i, 0]
- temp1 :=[input_sorted[i, 1]]
- j :=i + 1
- যদিও j
- টেম্প১-এর শেষে input_sorted[j, 1] ঢোকান
- j :=j + 1
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
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
আউটপুট
p
