Input: s ="cba"Output: 5Explanation: 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: 2Explanation: 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".
The number of operations is the number of lexicographically smaller permutations of s. For each position, count how many smaller characters can be swapped forward, and use factorials to count permutations, adjusting for duplicates.
#include<vector>#include<string>#include<algorithm>usingnamespace std;
constint MOD =1e9+7;
vector<longlong> fact, inv;
longlongmodpow(longlong a, longlong b) {
longlong res =1;
while (b) {
if (b &1) res = res * a % MOD;
a = a * a % MOD; b >>=1;
}
return res;
}
voidinit(int n) {
fact.assign(n+1, 1); inv.assign(n+1, 1);
for (int i =1; i <= n; ++i) fact[i] = fact[i-1] * i % MOD;
inv[n] = modpow(fact[n], MOD-2);
for (int i = n-1; i >=0; --i) inv[i] = inv[i+1] * (i+1) % MOD;
}
classSolution {
public:int makeStringSorted(string s) {
int n = s.size(); init(n);
vector<int> cnt(26, 0);
for (char c : s) cnt[c-'a']++;
longlong ans =0;
for (int i =0; i < n; ++i) {
for (int ch =0; ch < s[i]-'a'; ++ch) {
if (cnt[ch] ==0) continue;
cnt[ch]--;
longlong cur = fact[n-i-1];
for (int x : cnt) cur = cur * inv[x] % MOD;
ans = (ans + cur) % MOD;
cnt[ch]++;
}
cnt[s[i]-'a']--;
}
return ans;
}
};
import java.util.*;
classSolution {
staticfinalint MOD = 1000000007;
staticint[] fact, inv;
staticintmodpow(int a, int b) {
int res = 1;
while (b > 0) {
if ((b & 1) == 1) res = (int)((long)res * a % MOD);
a = (int)((long)a * a % MOD); b >>= 1;
}
return res;
}
staticvoidinit(int n) {
fact =newint[n+1]; inv =newint[n+1];
fact[0]= 1;
for (int i = 1; i <= n; ++i) fact[i]= (int)((long)fact[i-1]* i % MOD);
inv[n]= modpow(fact[n], MOD-2);
for (int i = n-1; i >= 0; --i) inv[i]= (int)((long)inv[i+1]* (i+1) % MOD);
}
publicintmakeStringSorted(String s) {
int n = s.length(); init(n);
int[] cnt =newint[26];
for (char c : s.toCharArray()) cnt[c-'a']++;
long ans = 0;
for (int i = 0; i < n; ++i) {
for (int ch = 0; ch < s.charAt(i)-'a'; ++ch) {
if (cnt[ch]== 0) continue;
cnt[ch]--;
long cur = fact[n-i-1];
for (int x : cnt) cur = cur * inv[x]% MOD;
ans = (ans + cur) % MOD;
cnt[ch]++;
}
cnt[s.charAt(i)-'a']--;
}
return (int)ans;
}
}
classSolution {
companionobject {
constval MOD = 1000000007lateinitvar fact: IntArray
lateinitvar inv: IntArray
funmodpow(a: Int, b: Int): Int {
var res = 1L; var aa = a.toLong(); var bb = b
while (bb > 0) {
if (bb and 1==1) res = res * aa % MOD
aa = aa * aa % MOD; bb = bb shr 1 }
return res.toInt()
}
funinit(n: Int) {
fact = IntArray(n+1); inv = IntArray(n+1)
fact[0] = 1for (i in1..n) fact[i] = (fact[i-1].toLong() * i % MOD).toInt()
inv[n] = modpow(fact[n], MOD-2)
for (i in n-1 downTo 0) inv[i] = (inv[i+1].toLong() * (i+1) % MOD).toInt()
}
}
funmakeStringSorted(s: String): Int {
val n = s.length; init(n)
val cnt = IntArray(26)
for (c in s) cnt[c-'a']++var ans = 0Lfor (i in0 until n) {
for (ch in0 until s[i]-'a') {
if (cnt[ch] ==0) continue cnt[ch]--var cur = fact[n-i-1].toLong()
for (x in cnt) cur = cur * inv[x] % MOD
ans = (ans + cur) % MOD
cnt[ch]++ }
cnt[s[i]-'a']-- }
return ans.toInt()
}
}
classSolution:
defmakeStringSorted(self, s: str) -> int:
MOD =10**9+7from math import factorial
n = len(s)
fact = [1]*(n+1)
for i in range(1, n+1): fact[i] = fact[i-1]*i % MOD
inv = [1]*(n+1)
inv[n] = pow(fact[n], MOD-2, MOD)
for i in range(n-1, -1, -1): inv[i] = inv[i+1]*(i+1)%MOD
cnt = [0]*26for c in s: cnt[ord(c)-97] +=1 ans =0for i in range(n):
for ch in range(ord(s[i])-97):
if cnt[ch] ==0: continue cnt[ch] -=1 cur = fact[n-i-1]
for x in cnt: cur = cur*inv[x]%MOD
ans = (ans + cur)%MOD
cnt[ch] +=1 cnt[ord(s[i])-97] -=1return ans
constMOD: i64=1_000_000_007;
fnmodpow(mut a: i64, mut b: i64) -> i64 {
letmut res =1;
while b >0 {
if b &1==1 { res = res * a %MOD; }
a = a * a %MOD; b >>=1;
}
res
}
fninit(n: usize) -> (Vec<i64>, Vec<i64>) {
letmut fact =vec![1; n+1];
letmut inv =vec![1; n+1];
for i in1..=n { fact[i] = fact[i-1] * i asi64%MOD; }
inv[n] = modpow(fact[n], MOD-2);
for i in (0..n).rev() { inv[i] = inv[i+1] * (i asi64+1) %MOD; }
(fact, inv)
}
impl Solution {
pubfnmake_string_sorted(s: String) -> i32 {
let n = s.len();
let (fact, inv) = init(n);
letmut cnt =vec![0; 26];
for c in s.bytes() { cnt[(c -b'a') asusize] +=1; }
letmut ans =0i64;
for (i, &c) in s.as_bytes().iter().enumerate() {
for ch in0..(c-b'a') {
if cnt[ch asusize] ==0 { continue; }
cnt[ch asusize] -=1;
letmut cur = fact[n-i-1];
for&x in&cnt { cur = cur * inv[x asusize] %MOD; }
ans = (ans + cur) %MOD;
cnt[ch asusize] +=1;
}
cnt[(c-b'a') asusize] -=1;
}
ans asi32 }
}