পাইথনে তিনটি শর্তের একটিটি পূরণ করার জন্য ন্যূনতম ক্যারেক্টার পরিবর্তন করার প্রোগ্রাম

আমাদের দুটি স্ট্রিং আছে s এবং t যাতে শুধু ছোট হাতের অক্ষর রয়েছে। এক অপারেশনে, আমরা s বা t-এর যেকোনো ক্যারেক্টারকে যেকোনো ছোট হাতের অক্ষরে পরিবর্তন করতে পারি। আমাদের নিচের তিনটি শর্তের যেকোনো একটি পূরণ করতে হবে:

s-এর প্রতিটি অক্ষর বর্ণমালায় t-এর প্রতিটি অক্ষর থেকে স্ট্রিক্টলি ছোট।
t-এর প্রতিটি অক্ষর বর্ণমালায় s-এর প্রতিটি অক্ষর থেকে স্ট্রিক্টলি ছোট।
s এবং t দুটোই শুধু একটি ডISTINCT অক্ষর থেকে গঠিত।

আমাদের ফলাফল পেতে ন্যূনতম অপারেশন সংখ্যা বের করতে হবে।

উদাহরণস্বরূপ, ইনপুট s = "sts", t = "uss" হলে আউটপুট হবে 2 কারণ:

যদি t-কে "uuu" বানাই ২ অপারেশনে, তবে s-এর সব অক্ষর t-এর সব অক্ষর থেকে ছোট।
যদি s-কে "ttt" এবং t-কে "sss" বানাই ৩ অপারেশনে, তবে t-এর সব অক্ষর s-এর সব অক্ষর থেকে ছোট।
যদি s-কে "sss" এবং t-কে "sss" বানাই ২ অপারেশনে, তবে s এবং t দুটোই একটি ডISTINCT অক্ষর থেকে গঠিত।

এখানে সেরা উপায় ২ অপারেশনে (১ নং বা ৩ নং)।

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

counter_s := s-এর ক্যারেক্টার ফ্রিকোয়েন্সি ম্যাপ
counter_t := t-এর ক্যারেক্টার ফ্রিকোয়েন্সি ম্যাপ
less_s := infinity, less_t := infinity, unique := infinity
accu_s := 0, accu_t := 0
ছোট হাতের ইংরেজি অক্ষর 'a' থেকে 'z' পর্যন্ত লুপ চালান:
- unique := min(unique, len(s) + len(t) - counter_s[c] - counter_t[c])
- যদি c > 'a' হয়, তবে:
  - less_s := min(less_s, len(s) - accu_s + accu_t)
  - less_t := min(less_t, len(t) - accu_t + accu_s)
- accu_s += counter_s[c]
- accu_t += counter_t[c]
min(less_s, less_t, unique) রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালোভাবে বুঝার জন্য:

from collections import Counter
import string
def solve(s, t):
    counter_s = Counter(s)
    counter_t = Counter(t)
    less_s, less_t, unique = float('inf'), float('inf'), float('inf')
    accu_s, accu_t = 0, 0
    for c in string.ascii_lowercase:
        unique = min(unique, len(s) + len(t) - counter_s[c] - counter_t[c])
        if c > 'a':
            less_s = min(less_s, len(s) - accu_s + accu_t)
            less_t = min(less_t, len(t) - accu_t + accu_s)
        accu_s += counter_s[c]
        accu_t += counter_t[c]
    return min(less_s, less_t, unique)

s = "sts"
t = "uss"
print(solve(s, t))

ইনপুট

"sts", "uss"