1830. Minimum Number of Operations to Make String Sorted LeetCode Solution
In this guide, you will get 1830. Minimum Number of Operations to Make String Sorted LeetCode Solution with the best time and space complexity. The solution to Minimum Number of Operations to Make String Sorted problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Number of Operations to Make String Sorted
You are given a string s (0-indexed). You are asked to perform the following operation on s until you get a sorted string:
Find the largest index i such that 1 <= i < s.length and s[i] < s[i – 1].
Find the largest index j such that i <= j < s.length and s[k] < s[i – 1] for all the possible values of k in the range [i, j] inclusive.
Swap the two characters at indices i – 1 and j.
Reverse the suffix starting at index i.
Return the number of operations needed to make the string sorted. Since the answer can be too large, return it modulo 109 + 7.
Example 1:
Input: s = “cba”
Output: 5
Explanation: The simulation goes as follows:
Operation 1: i=2, j=2. Swap s[1] and s[2] to get s=”cab”, then reverse the suffix starting at 2. Now, s=”cab”.
Operation 2: i=1, j=2. Swap s[0] and s[2] to get s=”bac”, then reverse the suffix starting at 1. Now, s=”bca”.
Operation 3: i=2, j=2. Swap s[1] and s[2] to get s=”bac”, then reverse the suffix starting at 2. Now, s=”bac”.
Operation 4: i=1, j=1. Swap s[0] and s[1] to get s=”abc”, then reverse the suffix starting at 1. Now, s=”acb”.
Operation 5: i=2, j=2. Swap s[1] and s[2] to get s=”abc”, then reverse the suffix starting at 2. Now, s=”abc”.
Input: s = “aabaa”
Output: 2
Explanation: The simulation goes as follows:
Operation 1: i=3, j=4. Swap s[2] and s[4] to get s=”aaaab”, then reverse the substring starting at 3. Now, s=”aaaba”.
Operation 2: i=4, j=4. Swap s[3] and s[4] to get s=”aaaab”, then reverse the substring starting at 4. Now, s=”aaaab”.
Constraints:
1 <= s.length <= 3000
s consists only of lowercase English letters.
Complexity Analysis
Time Complexity: O(26n) = O(n)
Space Complexity: O(n)
1830. Minimum Number of Operations to Make String Sorted LeetCode Solution in C++
class Solution {
public:
int makeStringSorted(string s) {
const int n = s.length();
const auto [fact, invFact] = getFactAndInvFact(n);
int ans = 0;
vector<int> count(26);
for (int i = n - 1; i >= 0; --i) {
const int order = s[i] - 'a';
++count[order];
long perm = accumulate(count.begin(), count.begin() + order, 0) *
fact[n - 1 - i] % kMod;
for (int j = 0; j < 26; ++j)
perm = perm * invFact[count[j]] % kMod;
ans = (ans + perm) % kMod;
}
return ans;
}
private:
static constexpr int kMod = 1'000'000'007;
pair<vector<long>, vector<long>> getFactAndInvFact(int n) {
vector<long> fact(n + 1);
vector<long> invFact(n + 1);
vector<long> inv(n + 1);
fact[0] = invFact[0] = 1;
inv[0] = inv[1] = 1;
for (int i = 1; i <= n; ++i) {
if (i >= 2)
inv[i] = kMod - kMod / i * inv[kMod % i] % kMod;
fact[i] = fact[i - 1] * i % kMod;
invFact[i] = invFact[i - 1] * inv[i] % kMod;
}
return {fact, invFact};
}
}; /* code provided by PROGIEZ */
1830. Minimum Number of Operations to Make String Sorted LeetCode Solution in Java
class Solution {
public int makeStringSorted(String s) {
final int kMod = 1_000_000_007;
final int n = s.length();
final long[][] factAndInvFact = getFactAndInvFact(n);
final long[] fact = factAndInvFact[0];
final long[] invFact = factAndInvFact[1];
int ans = 0;
int[] count = new int[26];
for (int i = n - 1; i >= 0; --i) {
final int order = s.charAt(i) - 'a';
++count[order];
long perm = Arrays.stream(count, 0, order).sum() * fact[n - 1 - i] % kMod;
for (int j = 0; j < 26; ++j)
perm = perm * invFact[count[j]] % kMod;
ans += perm;
ans %= kMod;
}
return ans;
}
private static final int kMod = 1_000_000_007;
private long[][] getFactAndInvFact(int n) {
long[] fact = new long[n + 1];
long[] invFact = new long[n + 1];
long[] inv = new long[n + 1];
fact[0] = invFact[0] = 1;
inv[0] = inv[1] = 1;
for (int i = 1; i <= n; ++i) {
if (i >= 2)
inv[i] = kMod - kMod / i * inv[kMod % i] % kMod;
fact[i] = fact[i - 1] * i % kMod;
invFact[i] = invFact[i - 1] * inv[i] % kMod;
}
return new long[][] {fact, invFact};
}
} // code provided by PROGIEZ
1830. Minimum Number of Operations to Make String Sorted LeetCode Solution in Python
class Solution:
def makeStringSorted(self, s: str) -> int:
kMod = 1_000_000_007
ans = 0
count = [0] * 26
@functools.lru_cache(None)
def fact(i: int) -> int:
return 1 if i <= 1 else i * fact(i - 1) % kMod
@functools.lru_cache(None)
def inv(i: int) -> int:
return pow(i, kMod - 2, kMod)
for i, c in enumerate(reversed(s)):
order = ord(c) - ord('a')
count[order] += 1
# count[:order] := s[i] can be any character smaller than c
# fact(i) := s[i + 1..n - 1] can be any sequence of characters
perm = sum(count[:order]) * fact(i)
for j in range(26):
perm = perm * inv(fact(count[j])) % kMod
ans = (ans + perm) % kMod
return ans # code by PROGIEZ
