মান ল করুন একটি s স্ট্রিং, আমরা বারবার প্রথম Konssekutiv ডুপ্লিকেট ক্যারেক্টারগুলো মুছে ফেলব। ফাইনাল স্ট্রিংটি খুঁজে বের করতে হবে।
যদি ইনপুট হয় s = "xyyyxxz", তবে আউটপুট হবে "z", কারণ "yyy" হল প্রথম Konssekutiv ডুপ্লিকেট ক্যারেক্টারগুলো যা মুছে যাবে। তাহলে থাকবে "xxxz"। তারপর "xxx" মুছে যাবে এবং "z" থাকবে।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:
- stack := একটি নতুন স্ট্যাক
- i := 0
- যখন i < s-এর আকার:
- যদি stack খালি না থাকে এবং stack-এর top s[i]-এর সমান হয়, তবে:
- x := stack-এর শেষ উপাদানটি মুছে ফেলুন
- যখন i < s-এর আকার এবং x == s[i], i := i + 1
- i := i - 1
- অন্যথায়,
- s[i] কে stack-এ পুশ করুন
- i := i + 1
- যদি stack খালি না থাকে এবং stack-এর top s[i]-এর সমান হয়, তবে:
- stack-এর উপাদানগুলো জয়েন করে ফেরত দিন।
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন:
উদাহরণ
class Solution: def solve(self, s): stack = [] i = 0 while i < len(s): if len(stack) and stack[-1] == s[i]: x = stack.pop() while i < len(s) and x == s[i]: i += 1 i -= 1 else: stack.append(s[i]) i += 1 return "".join(stack) ob = Solution() s = "xyyyxxz" print(ob.solve(s))
ইনপুট
"xyyyxxz"
আউটপুট
z
