পাইথনে স্ট্রিং থেকে এডজেসেন্ট ডুপ্লিকেট মুছে ফেলা (Remove All Adjacent Duplicates In String in Python)

সমস্যা বিবরণ

লোয়ারকেস লেটারের একটি স্ট্রিং S দেওয়া আছে। দুটি এডজেসেন্ট এবং সমান লেটার বেছে নিয়ে মুছে ফেলা হবে। এই প্রক্রিয়া কোনো ডুপ্লিকেট না থাকার পর্যন্ত চলবে। চূড়ান্ত স্ট্রিং ফেরত দিন।

উদাহরণ: "abbacaca" → "caca" (bb মুছে → aacaca → aa মুছে → caca)।

সমাধানের পদ্ধতি (স্ট্যাক ব্যবহার)

1. একটি স্ট্যাক (লিস্ট) এবং ইনডেক্স i = 0 নিন।
2. যখন i < len(S):
   • যদি স্ট্যাক খালি না হয় এবং স্ট্যাকের টপ == S[i]: স্ট্যাক থেকে পপ করুন, i++।
   • অন্যথায়: S[i] স্ট্যাকে পুশ করুন, i++।
3. স্ট্যাকের উপাদানগুলো জয়েন করে স্ট্রিং বানান এবং ফেরত দিন।

পাইথন উদাহরণ

class Solution(object):
    def removeDuplicates(self, S):
        stack = []
        for ch in S:
            if stack and stack[-1] == ch:
                stack.pop()
            else:
                stack.append(ch)
        return "".join(stack)

ob1 = Solution()
print(ob1.removeDuplicates("abbacaca"))

ইনপুট

"abbacaca"

আউটপুট

"caca"

টাইম ও স্পেস কমপ্লেক্সিটি

• টাইম: O(n) - প্রতিটি ক্যারেক্টার একবার প্রসেস হয়
• স্পেস: O(n) - সবচোয়ে খারাপ কেসে পুরো স্ট্রিং স্ট্যাকে যেতে পারে