ধরুন আমাদের একটি ছোট হাতের স্ট্রিং আছে যার দৈর্ঘ্য সমান। আমাদের এমন ন্যূনতম সংখ্যক অক্ষর খুঁজে বের করতে হবে যেগুলিকে আপডেট করতে হবে যাতে নিম্নলিখিত তিনটি শর্তের মধ্যে একটি সমস্ত i জন্য সন্তুষ্ট হয়, যেখানে 0 ≤ i
সুতরাং, যদি ইনপুটটি s ="ppppxxp" এর মত হয়, তাহলে আউটপুট হবে 1 কারণ আমরা যদি শেষ "p" কে "x" তে পরিবর্তন করি, তাহলে এটি s[i]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
from collections import Counter
from string import ascii_lowercase
def solve(s):
n = len(s)
left = Counter(s[: n >> 1])
right = Counter(s[n >> 1 :])
ans = n
for pivot in ascii_lowercase:
ans = min(ans, n - left[pivot] - right[pivot])
good = sum(left[c] for c in left if c <= pivot)
good += sum(right[c] for c in right if c > pivot)
ans = min(ans, n - good)
good = sum(left[c] for c in left if c > pivot)
good += sum(right[c] for c in right if c <= pivot)
ans = min(ans, n - good)
return ans
s = "pppxxp"
print(solve(s))
ইনপুট
"pppxxp"
আউটপুট
1
