Python में स्ट्रिंग को सॉर्ट करने के लिए न्यूनतम ऑपरेशन ज्ञात करें

एक स्ट्रिंग s दी गई है। निम्न ऑपरेशन दोहराएं जब तक स्ट्रिंग सॉर्ट न हो जाए:

1. सबसे बड़ा इंडेक्स i ढूंढें जहां 1 ≤ i < len(s) और s[i] < s[i-1]
2. सबसे बड़ा इंडेक्स j ढूंढें जहां i ≤ j < len(s) और सभी k ∈ [i, j] के लिए s[k] < s[i-1]
3. s[i-1] और s[j] को स्वैप करें
4. सफिक्स i से अंत तक रिवर्स करें

यह वास्तव में पिछला क्रमपरिवर्तन (previous permutation) एल्गोरिदम है। सॉर्ट होने तक के ऑपरेशन गिनें (मॉड्यूलो 10⁹+7)।

कुंजी अंतर्दृष्टि: क्रमपरिवर्तन रैंक

आवश्यक ऑपरेशन्स की संख्या = स्ट्रिंग की लेक्सिकोग्राफिक रैंक - 1 (सभी क्रमपरिवर्तनों में से सॉर्टेड पहला है)।

Python कार्यान्वयन

def min_operations_to_sort(s):
    MOD = 10**9 + 7
    n = len(s)
    
    # फैक्टरियल प्रीकंप्यूट
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i-1] * i % MOD
    
    # मॉड्यूलर व्युत्क्रम (फर्मेट का छोटा प्रमेय)
    inv_fact = [1] * (n + 1)
    inv_fact[n] = pow(fact[n], MOD - 2, MOD)
    for i in range(n, 0, -1):
        inv_fact[i-1] = inv_fact[i] * i % MOD
    
    # आवृत्ति गिनें
    from collections import Counter
    freq = Counter(s)
    
    rank = 0
    remaining = n
    
    for i, ch in enumerate(s):
        remaining -= 1
        # ch से छोटे अक्षरों के लिए
        for smaller_ch in sorted(freq.keys()):
            if smaller_ch >= ch:
                break
            if freq[smaller_ch] == 0:
                continue
            
            # smaller_ch को यहां रखने वाले क्रमपरिवर्तनों की संख्या
            freq[smaller_ch] -= 1
            perms = fact[remaining]
            for f in freq.values():
                perms = perms * inv_fact[f] % MOD
            rank = (rank + perms) % MOD
            freq[smaller_ch] += 1
        
        # वर्तमान अक्षर उपयोग करें
        freq[ch] -= 1
        if freq[ch] == 0:
            del freq[ch]
    
    return rank  # रैंक = ऑपरेशन्स (0-आधारित)

# परीक्षण
s = "ppqpp"
print(min_operations_to_sort(s))  # 2

सरल कार्यान्वयन (मूल कोड से)

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):  # रिवर्स क्रम में, इंडेक्स 1 से
        j = ord(c) - n
        d[j] += 1
        # a = (a + sum(d[:j]) * t // d[j]) % m
        # t = t * i // d[j]
        a = (a + sum(d[:j]) * t // d[j]) % m
        t = t * i // d[j]
    return a

print(solve("ppqpp"))  # 2

सरल कोड की व्याख्या

यह कोड फैक्टरियडिक नंबर सिस्टम का उपयोग करके रैंक की गणना करता है:

• d[j]: अक्षर j की आवृत्ति (अब तक प्रोसेस किए गए में)
• t: वर्तमान फैक्टरियल गुणक
• sum(d[:j]): वर्तमान अक्षर से छोटे अक्षरों की कुल संख्या
• t // d[j]: डुप्लिकेट अक्षरों के लिए विभाजन

उदाहरण ट्रेस (ppqpp)

क्रमपरिवर्तन: ppqpp → pppqp → ppppq (सॉर्टेड)। 2 ऑपरेशन्स।

जटिलता

• समय: O(n × 26) = O(n)
• स्थान: O(1) - निश्चित आकार सरणी