ধরুন আমাদের একটি ছোট হাতের স্ট্রিং আছে যার দৈর্ঘ্য সমান। আমাদের এমন ন্যূনতম সংখ্যক অক্ষর খুঁজে বের করতে হবে যেগুলিকে আপডেট করতে হবে যাতে নিম্নলিখিত তিনটি শর্তের মধ্যে একটি সমস্ত i জন্য সন্তুষ্ট হয়, যেখানে 0 ≤ i
- s[i]> s[j]
- s[i]
- s[i] ==s[j]
সুতরাং, যদি ইনপুটটি s ="ppppxxp" এর মত হয়, তাহলে আউটপুট হবে 1 কারণ আমরা যদি শেষ "p" কে "x" তে পরিবর্তন করি, তাহলে এটি s[i]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- n :=s এর আকার
- বাম :=s এর বাম অর্ধেক থেকে প্রতিটি অক্ষরের ফ্রিকোয়েন্সি সম্বলিত একটি অভিধান
- ডান :=s এর ডান অর্ধেক থেকে প্রতিটি অক্ষরের ফ্রিকোয়েন্সি সম্বলিত একটি অভিধান
- উত্তর :=n
- ছোট হাতের ইংরেজি অক্ষরে প্রতিটি অক্ষর পিভটের জন্য, করুন
- উত্তর :=সর্বনিম্ন উত্তর এবং (n - বাম [পিভট] - ডান [পিভট])
- ভাল :=উপস্থিত সমস্ত উপাদানের সমষ্টি (বামদিকে প্রতিটি গ এর জন্য যদি c <=পিভট)
- ভাল :=ভাল + ডানদিকে উপস্থিত সমস্ত উপাদানের যোগফল [c] ডানদিকে প্রতিটি c এর জন্য যদি c> পিভট
- উত্তর :=সর্বনিম্ন উত্তর এবং (n - ভাল)
- ভাল :=বামদিকে উপস্থিত সকল উপাদানের যোগফল [c] বাম দিকে প্রতিটি c এর জন্য যদি c> পিভট
- ভাল :=ভাল + ডানদিকে উপস্থিত সমস্ত উপাদানের যোগফল[c] ডানদিকে প্রতিটি c এর জন্য যদি c <=পিভট
- উত্তর :=সর্বনিম্ন উত্তর এবং (n - ভাল)
- উত্তর ফেরত দিন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
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