পাইথনে 'A' গুলো 'B' গুলোর আগে আনতে ন্যূনতম ক্যারেক্টার ডিলিট করার প্রোগ্রাম

ধরা যাক s নামক একটি স্ট্রিং রয়েছে যেটিতে শুধু 'A' এবং 'B' অক্ষর রয়েছে। আমাদের স্ট্রিং থেকে ন্যূনতম কতগুলো ক্যারেক্টার ডিলিট করলে সব 'A' গুলো সব 'B' গুলোর আগে চলে আসবে তা বের করতে হবে।

উদাহরণ

ইনপুট: S = "AABAABB"

আউটপুট: 1

ব্যাখ্যা: শেষ 'A' টি মুছে দিলে "AABBB" হয় যেটিতে সব 'A' গুলো 'B' গুলোর আগে।

সমাধানের ধাপসমূহ

1. a_right := s-এ 'A' এর সংখ্যা
2. b_left := 0
3. ans := a_right
4. প্রতিটি ইন্ডেক্স i এবং ক্যারেক্টার c এর জন্য s-এ:
   • যদি c == "A" হয়, তবে a_right -= 1
   • অন্যথায় (c == "B"), b_left += 1
   • ans := min(ans, a_right + b_left)
5. ans ফেরত দিন

পাইথন ইমপ্লিমেন্টেশন

class Solution:
    def solve(self, s):
        a_right = s.count("A")
        b_left = 0
        ans = a_right
        for i, c in enumerate(s):
            if c == "A":
                a_right -= 1
            else:
                b_left += 1
            ans = min(ans, a_right + b_left)
        return ans

ob = Solution()
S = "AABAABB"
print(ob.solve(S))

ইনপুট

"AABAABB"

আউটপুট

1