পাইথনে স্ট্রিংকে হাফ-মোনোটোনাস बनाने এর জন্য ন্যূনতম আপডেট গণনা করার প্রোগ্রাম

পাইথনে একটি লোয়ারকেস স্ট্রিং s দেওয়া আছে যার দৈর্ঘ্য জোড়। স্ট্রিংটি দুটি সমান ভাগে ভাগ করলে (বাম পাশ এবং ডান পাশ), ন্যূনতম কতটি ক্যারেক্টার আপডেট করলে নিচের তিনটি শর্তের যেকোনো একটি সব জোড়া (i, j) এর জন্য সন্তুষ্ট হবে, সেটি বের করতে হবে।

যেখানে 0 ≤ i < n/2 এবং n/2 ≤ j < n:

1. s[i] > s[j] (বাম পাশ সবসময় বড়)
2. s[i] < s[j] (বাম পাশ সবসময় ছোট)
3. s[i] == s[j] (উভয় পাশ সমান)

উদাহরণ

ইনপুট: s = "pppxxp"

আউটপুট: 1

কারণ শেষ 'p' কে 'x' করে দিলে বাম পাশ (ppp) সবসময় ডান পাশ (xxx) থেকে ছোট হয় -> শর্ত ২ সন্তুষ্ট।

এলগরিদম

1. n = len(s)
2. left = Counter(s[:n//2]), right = Counter(s[n//2:]) — দুটি হাফের ক্যারেক্টার ফ্রিকোয়েন্সি।
3. ans = n (ওয়ার্স্ট কেস: সব ক্যারেক্টার পরিবর্তন)
4. প্রতিটি পিভট ক্যারেক্টার 'a' থেকে 'z' পর্যন্ত:
   • শর্ত ৩ (সমান): ans = min(ans, n - left[pivot] - right[pivot]) — পিভট ক্যারেক্টারের বাইর সবগুলো পরিবর্তন।
   • শর্ত ২ (বাম < ডান):
     • good = sum(left[c] for c in left if c <= pivot) + 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) + sum(right[c] for c in right if c <= pivot)
     • ans = min(ans, n - good)
5. ans রিটার্ন করুন

পাইথন ইমপ্লিমেন্টেশন

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))  # Output: 1

ইনপুট

"pppxxp"

আউটপুট

1

ব্যাখ্যা

• স্ট্রিং: "pppxxp" -> বাম: "ppp" (p:3), ডান: "xxp" (x:2, p:1)
• পিভট 'p' দিয়ে চেক:
  • শর্ত ৩: n - left['p'] - right['p'] = 6 - 3 - 1 = 2
  • শর্ত ২ (বাম <= p, ডান > p): good = left['p'](3) + right['x'](2) = 5 -> n - good = 1 ✓
  • শর্ত ১ (বাম > p, ডান <= p): good = 0 + right['p'](1) = 1 -> n - good = 5
• ন্যূনতম = 1

সময় জটিলতা: O(n + 26 × alphabet) ≈ O(n) — খুব দক্ষ।