पायथन में विशिष्ट वर्णों का सबसे छोटा अनुक्रम

मान लीजिए कि हमारे पास एक टेक्स्ट है, हमें टेक्स्ट के लेक्सिकोग्राफ़िक रूप से सबसे छोटे अनुक्रम को ढूंढना है जिसमें टेक्स्ट के सभी अलग-अलग वर्ण बिल्कुल एक बार होते हैं। तो अगर इनपुट “cdadabcc” जैसा है, तो आउटपुट “adbc” होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक स्टैक सेंट को परिभाषित करें, दो नक्शे last_o और माना जाता है, वे शुरू में खाली हैं
• पाठ्यक्रम की लंबाई में i के लिए - 1 से 0 तक
  • अगर टेक्स्ट[i] last_o में मौजूद नहीं है -
    • last_o[text[i]] :=i
    • माना जाता है[पाठ[i]]:=झूठा
  • मैं :=0
  • जबकि मैं <पाठ की लंबाई
    • यदि स्टैक में कोई तत्व नहीं है
      • पाठ को पुश करें[i] स्टैक में
      • माना जाता है[पाठ[i]] :=सच
      • मैं 1 से बढ़ाएँ
    • अन्यथा स्टैक टॉप> टेक्स्ट[i] और माना जाता है[text[i]] गलत है
      • अगर last_o[स्टैक टॉप]> i
        • माना जाता है [स्टैक टॉप एलिमेंट] :=असत्य
        • स्टैक से पॉप
      • अन्यथा
        • माना जाता है[tex[i]] =सच
        • पाठ सम्मिलित करें[i] स्टैक में
        • मैं 1 से बढ़ाएँ
    • अन्यथा जब स्टैक शीर्ष तत्व
    • पाठ सम्मिलित करें[i] स्टैक में
    • माना जाता है[पाठ[i]] :=सच
    • मैं 1 से बढ़ाएँ
  • अन्यथा 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"