পাইথনে সাদৃশ্য শেষে মুছে স্ট্রিং-এর ন্যূনতম দৈর্ঘ্য বের করার প্রোগ্রাম

মান লিজিয়ে আমাদের একটি স্ট্রিং আছে s যাতে শুধু 'a', 'b', 'c' এই তিনটি ক্যারেক্টার রয়েছে। আমরা নিচের অ্যালগরিদমটি স্ট্রিংয়ে যেকোনো সংখ্যক বার প্রয়োগ করতে পারি:

s-এর একটি নন-ইম্পটি প্রিফিক্স বাছাই করুন যেখানে সকল ক্যারেক্টার একই।
s-এর একটি নন-ইম্পটি সাফিক্স বাছাই করুন যেখানে সকল ক্যারেক্টার একই।
প্রিফিক্স এবং সাফিক্স ডিজয়েন্ট (disjoint) হবে।
প্রিফিক্স ও সাফিক্স-এর ক্যারেক্টার একই হতে হবে।
প্রিফিক্স এবং সাফিক্স দুটোই s-থেকে মুছে দিন।

শেষে, উপরের অপারেশন যেকোনো সংখ্যকবার (হয় শূন্যবার) প্রয়োগ করার পর s-এর ন্যূনতম দৈর্ঘ্য বের করতে হবে।

যেমন, ইনপুট হলে s = "aabccabba", তবে আউটপুট হবে 3 কারণ প্রথমে আমরা প্রিফিক্স = "aa" এবং সাফিক্স = "a" বাছাই করতে পারি, মুছলে স্ট্রিং হবে "bccabb"। তারপর প্রিফিক্স = "b" এবং সাফিক্স = "bb" বাছাই করলে স্ট্রিং হবে "cca", যার দৈর্ঘ্য ৩।

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

s := deque(s) দিয়ে একটি কিউ তৈরি করুন।
len(s) > 1 and s[0] == s[-1] থাকা পর্যন্ত:
- chk := s[0]
- s খালি না হয় এবং s[0] == chk থাকা পর্যন্ত: s.popleft()
- s খালি না হয় এবং s[-1] == chk থাকা পর্যন্ত: s.pop()
len(s) রিটার্ন করুন।

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন:

from collections import deque
def solve(s):
    s = deque(s)
    while len(s) > 1 and s[0] == s[-1]:
        chk = s[0]
        while s and s[0] == chk:
            s.popleft()
        while s and s[-1] == chk:
            s.pop()
    return len(s)

s = "aabccabba"
print(solve(s))

ইনপুট

"aabccabba"