Python-এ স্ট্রিং সাজানোর জন্য ন্যূনতম অপারেশন বের করার প্রোগ্রাম

মনে করুন আমাদের কাছে একটি স্ট্রিং s আছে। স্ট্রিংটি সাজানো পর্যন্ত আমরা s-এ নিচের অপারেশনটি করতে থাকব −

সবচেয়ে বড় ইন্ডেক্স i সিলেক্ট করুন যাতে 1 <= i < s-এর দৈর্ঘ্য এবং s[i] < s[i - 1]।
সবচেয়ে বড় ইন্ডেক্স j সিলেক্ট করুন যাতে i <= j < s-এর দৈর্ঘ্য এবং s[k] < s[i - 1] i থেকে j পর্যন্ত সব সম্ভাব্য k মান জন্য।
i-1 এবং j ইন্ডেক্সের দুটি ক্যারেক্টার এক্সচেঞ্জ করুন।
ইন্ডেক্স i থেকে সাফিক্স রিভার্স করুন।

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

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

প্রথম অপারেশনে, i=3, j=4। s[2] এবং s[4] এক্সচেঞ্জ করলে s="ppppq", তারপর ইন্ডেক্স 3 থেকে সাবস্ট্রিং রিভার্স। এখন, s="pppqp"।
দ্বিতীয় অপারেশনে, i=4, j=4। s[3] এবং s[4] এক্সচেঞ্জ করলে s="ppppq", তারপর ইন্ডেক্স 4 থেকে সাবস্ট্রিং রিভার্স। এখন, s = "ppppq"।

এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব −

d := ২৬ আকারের একটি অ্যারে 0 দিয়ে পূরণ
a := 0, t := 1
m := 10^9 + 7
n := 'a'-র ASCII
s-র প্রতিটি ইন্ডেক্স i এবং ক্যারেক্টর c-এর জন্য রিভার্স অর্ডারে, ইন্ডেক্স 1 থেকে শুরু করে, করুন
- j := c-এর ASCII - n
- d[j] := d[j] + 1
- a := (a + d[0 থেকে j-1] এর সব এলিমেন্টের সমষ্টি) * t/d[j] এর ভাগফল) mod m
- t := t * i/d[j] এর ভাগফল
a রিটার্ন করুন

উদাহরণ

বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন

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"