পাইথনে স্ট্রিং সাজানোর জন্য ন্যূনতম সংখ্যক অপারেশন খুঁজে বের করার প্রোগ্রাম

স্ট্রিং সাজানোর জন্য আমাদের প্রয়োজনীয় অপারেশনের সংখ্যা খুঁজে বের করতে হবে। উত্তরটি খুব বড় হতে পারে তাই ফলাফল মডিউল 10^9 + 7 ফেরত দিন।

সুতরাং, যদি ইনপুট s ="ppqpp" এর মত হয়, তাহলে আউটপুট হবে 2 কারণ

• প্রথম অপারেশনে, i=3, j=4। s="ppppq" পেতে s[2] এবং s[4] বিনিময় করুন, তারপর সূচক 3 থেকে সাবস্ট্রিংটি বিপরীত করুন। এখন, s="pppqp"।

• দ্বিতীয় অপারেশনে, i=4, j=4। s="ppppq" পেতে s[3] এবং s[4] বিনিময় করুন, তারপর ইনডেক্স 4 থেকে সাবস্ট্রিংটি বিপরীত করুন, Now, s ="ppppq"।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• d :=26 আকারের একটি অ্যারে এবং 0 দিয়ে পূরণ করুন

• a :=0, t :=1

• m :=10^9 + 7

• n :='a'

  এর ASCII

• প্রতিটি সূচক i এবং অক্ষর c এর বিপরীত ক্রমে, সূচী 1 থেকে শুরু করুন, করুন

  • j :=c - n

    এর ASCII

  • d[j] :=d[j] + 1

  • a :=(a + d এর সমস্ত উপাদানের যোগফল [সূচী 0 থেকে j-1]) * t/d[j] এর ভাগফল) mod m

  • t :=t * i/d[j]

    এর ভাগফল

• একটি ফেরত দিন

উদাহরণ

আসুন আরও ভালভাবে বোঝার জন্য নিম্নলিখিত বাস্তবায়ন দেখি

def solve(s):
   d = [0]*26
   a = 0
   t = 1
   m = 10**9 + 7
   n = ord('a')
   for i,c in enumerate(s[::-1],1):
      j = ord(c) - n
      d[j] += 1
      a = (a+sum(d[:j])*t//d[j]) % m
      t = t*i//d[j]
   return a

s = "ppqpp"
print(solve(s))

ইনপুট

"ppqpp"

আউটপুট

2