Problem
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 that1 <= i < s.length
ands[i] < s[i - 1]
.Find the largest index
j
such thati <= j < s.length
ands[k] < s[i - 1]
for all the possible values ofk
in the range[i, j]
inclusive.Swap the two characters at indices
i - 1
andj
.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 10^9 + 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".
Example 2:
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.
Solution
class Solution {
public int makeStringSorted(String s) {
int n = s.length();
int[] count = new int[26];
for (int i = 0; i < n; i++) {
count[s.charAt(i) - 'a']++;
}
long[] fact = new long[n + 1];
fact[0] = 1;
int mod = 1000000007;
for (int i = 1; i <= n; i++) {
fact[i] = (fact[i - 1] * i) % mod;
}
int len = n;
long ans = 0;
for (int i = 0; i < n; i++) {
len--;
int bound = s.charAt(i) - 'a';
int first = 0;
long rev = 1;
for (int k = 0; k < 26; k++) {
if (k < bound) {
first += count[k];
}
rev = (rev * fact[count[k]]) % mod;
}
ans =
ans % mod
+ (((first * fact[len]) % mod)
* (modPow(rev, (long) mod - 2, mod))
% mod)
% mod;
ans = ans % mod;
count[bound]--;
}
return (int) ans;
}
private long modPow(long x, long n, int m) {
long result = 1;
while (n > 0) {
if ((n & 1) != 0) {
result = (result * x) % m;
}
x = (x * x) % m;
n = n >> 1;
}
return result;
}
}
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).