পাইথনে স্বতন্ত্র অক্ষরের ক্ষুদ্রতম অনুবর্তন

ধরুন আমাদের কাছে একটি পাঠ্য আছে, আমাদেরকে পাঠ্যের আভিধানিকভাবে ক্ষুদ্রতম অনুগামীটি খুঁজে বের করতে হবে যাতে পাঠ্যের সমস্ত স্বতন্ত্র অক্ষর ঠিক একবার রয়েছে। তাই ইনপুট যদি "cdadabcc" এর মত হয়, তাহলে আউটপুট হবে "adbc"।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি স্ট্যাক st সংজ্ঞায়িত করুন, দুটি মানচিত্র last_o এবং বিবেচনা করুন, তারা প্রাথমিকভাবে ফাঁকা
• আমি পাঠ্যের পরিসরের দৈর্ঘ্য - 1 থেকে 0
  পর্যন্ত
  • যদি টেক্সট[i] last_o −
    -এ উপস্থিত না থাকে
    • last_o[text[i]] :=i
    • বিবেচিত [টেক্সট[i]] :=মিথ্যা
  • i :=0
  • যখন আমি <পাঠ্যের দৈর্ঘ্য
    • যদি স্ট্যাকের কোনো উপাদান না থাকে
      • স্ট্যাকে টেক্সট [i] পুশ করুন
      • বিবেচিত [টেক্সট[i]] :=সত্য
      • i 1 দ্বারা বাড়ান
    • অন্যথায় স্ট্যাক টপ> text[i] এবং বিবেচিত [text[i]] মিথ্যা
      • যদি last_o[স্ট্যাক টপ]> i
        • বিবেচিত [স্ট্যাক শীর্ষ উপাদান] :=মিথ্যা
        • স্ট্যাক থেকে পপ
      • অন্যথায়
        • বিবেচিত[tex[i]] =সত্য
        স্ট্যাকের মধ্যে
        • টেক্সট [i] সন্নিবেশ করান
        • i 1 দ্বারা বাড়ান
    • অন্যথায় যখন স্ট্যাক শীর্ষ উপাদান স্ট্যাকের মধ্যে
    • টেক্সট [i] সন্নিবেশ করান
    • বিবেচিত [টেক্সট[i]] :=সত্য
    • i 1 দ্বারা বাড়ান
  • অন্যথায় i 1 দ্বারা বাড়ান

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

class Solution(object):
   def smallestSubsequence(self, text):
      """
      :type text: str
      :rtype: str
      """
      stack = []
      last_o = {}
      considered = {}
      for i in range(len(text)-1,-1,-1):
         if text[i] not in last_o:
            last_o[text[i]] = i
            considered[text[i]] = False
      print(last_o)
      i = 0
      while i < len(text):
         print(stack,i,text[i])
         if len(stack) == 0:
            stack.append(text[i])
            considered[text[i]] = True
            i+=1
         elif stack[-1]>text[i] and considered[text[i]] == False:
            if last_o[stack[-1]]>i:
               considered[stack[-1]]=False
               stack.pop()
            else:
               considered[text[i]] = True
               stack.append(text[i])
               i+=1
         elif stack[-1]<text[i] and considered[text[i]] == False:
            stack.append(text[i])
            considered[text[i]] = True
            i+=1
         else:
            i+=1
      return "".join(i for i in stack)

ইনপুট

"cdadabcc"

আউটপুট

"adbc"