पायथन में डिस्टिंक्ट कैरेक्टर्स की सबसे छोटी सबसीक्वेंस

मान लीजिए हमारे पास एक टेक्स्ट है, हमें टेक्स्ट की लेक्सिकोग्राफिकली सबसे छोटी सबसीक्वेंस ढूंढनी है जिसमें टेक्स्ट के सभी डिस्टिंक्ट कैरेक्टर्स ठीक एक बार हों। इसलिए यदि इनपुट \"cdadabcc\" जैसा है, तो आउटपुट \"adbc\" होगा।

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

• एक स्टैक st परिभाषित करें, दो मैप last_o और considered, वे प्रारंभ में खाली हैं
• i को टेक्स्ट की लंबाई - 1 से 0 तक डाउन टू रेंज में
  • यदि text[i] last_o में मौजूद नहीं है -
    • last_o[text[i]] := i
    • considered[text[i]] := false
  • i := 0
  • जब तक i < टेक्स्ट की लंबाई
    • यदि स्टैक में कोई एलिमेंट नहीं है
      • text[i] को स्टैक में पुश करें
      • considered[text[i]] := true
      • i को 1 से बढ़ाएं
    • अन्यथा स्टैक टॉप > text[i] और considered[text[i]] false है
      • यदि last_o[स्टैक टॉप] > i
        • considered[स्टैक टॉप एलिमेंट] := false
        • स्टैक से पॉप करें
      • अन्यथा
        • considered[tex[i]] = true
        • text[i] को स्टैक में इन्सर्ट करें
        • i को 1 से बढ़ाएं
    • अन्यथा जब स्टैक टॉप एलिमेंट < text[i] और considered[text[i]] = false
      • text[i] को स्टैक में इन्सर्ट करें
      • considered[text[i]] := true
      • 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]
  इनपुट
  \"cdadabcc\"
  आउटपुट
  \"adbc\"