We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Operations to Make String Sorted

Number: 1941

Difficulty: Hard

Paid? No

Companies: Samsung

Problem Description

Given a string s, you are allowed to repeatedly perform the following operation until s becomes sorted in non‐decreasing order:

  1. Find the largest index i (1 <= i < s.length) such that s[i] < s[i - 1].
  2. Find the largest index j (i <= j < s.length) such that for every k in the range [i, j], s[k] < s[i - 1].
  3. Swap s[i - 1] and s[j].
  4. Reverse the substring of s starting at index i. Return the number of operations required to make s sorted. It turns out that this number is equivalent to the count of distinct permutations (among all permutations of s with duplicates accounted for) that come before s in lexicographical order. Since the answer can be very large, return it modulo 10^9 + 7.

Key Insights

  • The problem is equivalent to finding the lexicographic rank of the string among all its distinct permutations.
  • Due to duplicate characters, the total number of distinct permutations is computed using factorials divided by the factorial of the frequency counts.
  • To compute the contribution of each character, precompute factorials and modular inverses up to the length of s.
  • Use a frequency counter for the letters and decrement counts as you fix positions one by one.

Space and Time Complexity

Time Complexity: O(n * 26) where n is the length of s, iterating over each character and checking a constant number (26) of letters. Space Complexity: O(n + C) where n is for factorial precomputation and C is constant (26) for the frequency counter.

Solution

The solution computes the lexicographic rank of the string, which represents the number of distinct permutations that appear before the given string when all permutations are listed in sorted order. To solve this:

  1. Precompute factorials and their modular inverses for numbers up to n (length of s) using a modulus mod = 10^9+7.
  2. Create an array to count the frequency of each character in s.
  3. Loop over each character in s and for every smaller character (in lexicographical order) that is still available in the frequency array, compute the number of valid permutations if that smaller character were placed at the current position.
  4. The number of valid permutations is computed as: factorial(remaining_length) multiplied by the modular inverse of the product of factorials of each frequency.
  5. Decrement the frequency of the current character and continue until the entire string is processed.
  6. The sum of all contributions gives the number of operations required.

The careful use of modular arithmetic and precomputation ensures the solution is efficient even for the maximum input size.

Code Solutions

MOD = 10**9 + 7

# Precompute factorials and inverses up to n
def precompute_factorials(n, mod):
    fact = [1] * (n + 1)
    inv_fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i % mod
    inv_fact[n] = pow(fact[n], mod - 2, mod)
    for i in range(n - 1, -1, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod
    return fact, inv_fact

def makeStringSorted(s: str) -> int:
    n = len(s)
    fact, inv_fact = precompute_factorials(n, MOD)
    # Frequency of each lowercase letter
    freq = [0] * 26
    for ch in s:
        freq[ord(ch) - ord('a')] += 1

    ans = 0
    # Iterate through each character in the string.
    for i in range(n):
        # For each character smaller than s[i]
        cur = ord(s[i]) - ord('a')
        for j in range(cur):
            if freq[j] == 0:
                continue
            # Use one occurrence of the letter j instead of s[i]
            freq[j] -= 1
            # Compute the number of permutations of the remaining characters.
            perms = fact[n - i - 1]
            for count in freq:
                perms = perms * inv_fact[count] % MOD
            ans = (ans + perms) % MOD
            freq[j] += 1  # Restore the frequency
        # Deduct the frequency of the current letter since we fix it at i
        freq[cur] -= 1

    return ans

# Example usage
print(makeStringSorted("cba"))  # Output: 5
← Back to All Questions