পাইথনে দুটি স্ট্রিং সমান করার জন্য ন্যূনতম প্রি-প্রসেসিং মুভ গণনা

একই দৈর্ঘ্যের দুটি স্ট্রিং P এবং Q দেওয়া আছে (শুধু ছোট হাতের অক্ষর)। P-তে ন্যূনতম কতগুলো প্রি-প্রসেসিং মুভ (ক্যারেক্টার পরিবর্তন) দরকার যাতে পরবর্তীতে নিচের অপারেশনগুলো ব্যবহার করে P এবং Q সমান করা যায়:

• ইনডেক্স i-এ P[i] এবং Q[i] স왑 করা।
• ইনডেক্স i-এ P[i] এবং P[n-i-1] স왑 করা।
• ইনডেক্স i-এ Q[i] এবং Q[n-i-1] সপ করা।

এক মুভে P-এর যেকোনো একটি ক্যারেক্টার ইংরেজি বর্ণমালার যেকোনো অন্য ক্যারেক্টারে বদলানো যায়।

উদাহরণ

ইনপুট: P = "pqprpqp", Q = "qprpqpp"

আউটপুট: 4

ব্যাখ্যা: P[0]='q', P[2]='r', P[3]='p', P[4]='q' বদলালে P হয় "qqrpqqp"। এরপর swap(P1,Q1) এবং swap(P1,P5) দিয়ে সমান করা যায়।

সমাধানের পদ্ধতি

1. স্ট্রিং-এর আধা অংশ পর্যন্ত লুপ চালানো হয় (i = 0 থেকে n/2-1)।
2. প্রতিটি i-তে P[i], P[n-i-1], Q[i], Q[n-i-1] — এই চারটি ক্যারেক্টার বিশ্লেষণ করা হয়।
3. এই চারটি ক্যারেক্টারর ইউনিক (unique) সংখ্যা গণনা করা হয়।
4. ইউনিক সংখ্যা অনুযায়ী প্রি-প্রসেসিং মুভ যোগ করা হয়:
   • ৪টি ইউনিক হলে → ২ মুভ
   • ৩টি ইউনিক হলে → ১ + (P[i]==P[n-i-1] ? 1 : 0) মুভ
   • ২টি ইউনিক হলে → (P[i] এর ফ্রিকোয়েন্সি != 2) ? 1 : 0 মুভ
5. যদি স্ট্রিং-এর দৈর্ঘ্য বিজোড় হয় এবং মাঝপথের ক্যারেক্টারগুলো ভিন্ন হয়, তবে ১ মুভ যোগ করা হয়।

পাইথন কোড

def count_preprocess(P, Q):
    n = len(P)
    res = 0
    for i in range(n // 2):
        my_map = {}
        my_map[P[i]] = 1
        if P[i] == P[n - i - 1]:
            my_map[P[n - i - 1]] += 1
        if Q[i] in my_map:
            my_map[Q[i]] += 1
        else:
            my_map[Q[i]] = 1
        if Q[n - i - 1] in my_map:
            my_map[Q[n - 1 - i]] += 1
        else:
            my_map[Q[n - 1 - i]] = 1
        
        size = len(my_map)
        if size == 4:
            res += 2
        elif size == 3:
            res += 1 + (P[i] == P[n - i - 1])
        elif size == 2:
            res += (my_map[P[i]] != 2)
    
    if n % 2 == 1 and P[n // 2] != Q[n // 2]:
        res += 1
    return res

A = "pqprpqp"
B = "qprpqpp"
print(count_preprocess(A, B))

ইনপুট

"pqprpqp", "qprpqpp"

আউটপুট

4