পাইথনে স্মলেস্ট সাবসিকোয়েন্স অফ ডিস্টিংক্ট ক্যারেক্টার

মনে করুন আমাদের একটি টেক্সট আছে, আমাদের টেক্সটের সব ডিস্টিংক্ট ক্যারেক্টার ঠিক একবার ধারণ করে লেক্সিকোগ্রাফিক্যালি স্মলেস্ট সাবসিকোয়েন্স বের করতে হবে। ইনপুট যদি "cdadabcc" হয়, তবে আউটপুট হবে "adbc"।

এটি সমাধান করতে আমরা নিচের ধাপগুলো ফলো করব (স্ট্যাক + লালচী পদ্ধতি):

• stack, last_o, considered দুটি ম্যাপ ডিফাইন করুন (প্রাথমিকভাবে খালি)।

• for i in range len(text)-1 down to 0:

  • যদি text[i] last_o-এ না থাকে:

    • last_o[text[i]] := i

    • considered[text[i]] := false

• i := 0

• while i < len(text):

  • যদি স্ট্যাক খালি হয়:

    • push text[i]

    • considered[text[i]] := true, i++

  • অন্যথায় যদি stack[-1] > text[i] এবং considered[text[i]] == false:

    • যদি last_o[stack[-1]] > i:

      • considered[stack[-1]] := false, stack.pop()

    • অন্যথায়:

      • considered[text[i]] = true, stack.append(text[i]), i++

  • অন্যথায় যদি stack[-1] < text[i] এবং considered[text[i]] == false:

    • stack.append(text[i]), considered[text[i]] := true, i++

  • অন্যথায় i++

• স্ট্যাকের সব এলিমেন্ট রিভার্স অর্ডারে স্ট্রিং হিসেবে রিটার্ন করুন।

উদাহরণ

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"