Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
You are given a string s (0-indexed). You are asked to perform the following operation on s until you get a sorted string:
i such that 1 <= i < s.length and s[i] < s[i - 1].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.i - 1 and j.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".
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 <= 3000s consists only of lowercase English letters.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map · Math
"cba"
"aabaa"
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1830: Minimum Number of Operations to Make String Sorted
class Solution {
private static final int N = 3010;
private static final int MOD = (int) 1e9 + 7;
private static final long[] f = new long[N];
private static final long[] g = new long[N];
static {
f[0] = 1;
g[0] = 1;
for (int i = 1; i < N; ++i) {
f[i] = f[i - 1] * i % MOD;
g[i] = qmi(f[i], MOD - 2);
}
}
public static long qmi(long a, int k) {
long res = 1;
while (k != 0) {
if ((k & 1) == 1) {
res = res * a % MOD;
}
k >>= 1;
a = a * a % MOD;
}
return res;
}
public int makeStringSorted(String s) {
int[] cnt = new int[26];
int n = s.length();
for (int i = 0; i < n; ++i) {
++cnt[s.charAt(i) - 'a'];
}
long ans = 0;
for (int i = 0; i < n; ++i) {
int m = 0;
for (int j = s.charAt(i) - 'a' - 1; j >= 0; --j) {
m += cnt[j];
}
long t = m * f[n - i - 1] % MOD;
for (int v : cnt) {
t = t * g[v] % MOD;
}
--cnt[s.charAt(i) - 'a'];
ans = (ans + t + MOD) % MOD;
}
return (int) ans;
}
}
// Accepted solution for LeetCode #1830: Minimum Number of Operations to Make String Sorted
const n = 3010
const mod = 1e9 + 7
var f = make([]int, n)
var g = make([]int, n)
func qmi(a, k int) int {
res := 1
for k != 0 {
if k&1 == 1 {
res = res * a % mod
}
k >>= 1
a = a * a % mod
}
return res
}
func init() {
f[0], g[0] = 1, 1
for i := 1; i < n; i++ {
f[i] = f[i-1] * i % mod
g[i] = qmi(f[i], mod-2)
}
}
func makeStringSorted(s string) (ans int) {
cnt := [26]int{}
for _, c := range s {
cnt[c-'a']++
}
for i, c := range s {
m := 0
for j := int(c-'a') - 1; j >= 0; j-- {
m += cnt[j]
}
t := m * f[len(s)-i-1] % mod
for _, v := range cnt {
t = t * g[v] % mod
}
ans = (ans + t + mod) % mod
cnt[c-'a']--
}
return
}
# Accepted solution for LeetCode #1830: Minimum Number of Operations to Make String Sorted
n = 3010
mod = 10**9 + 7
f = [1] + [0] * n
g = [1] + [0] * n
for i in range(1, n):
f[i] = f[i - 1] * i % mod
g[i] = pow(f[i], mod - 2, mod)
class Solution:
def makeStringSorted(self, s: str) -> int:
cnt = Counter(s)
ans, n = 0, len(s)
for i, c in enumerate(s):
m = sum(v for a, v in cnt.items() if a < c)
t = f[n - i - 1] * m
for v in cnt.values():
t = t * g[v] % mod
ans = (ans + t) % mod
cnt[c] -= 1
if cnt[c] == 0:
cnt.pop(c)
return ans
// Accepted solution for LeetCode #1830: Minimum Number of Operations to Make String Sorted
/**
* [1830] 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:
* <ol>
* 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.
* </ol>
* 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.
*
*/
pub struct Solution {}
// problem: https://leetcode.com/problems/minimum-number-of-operations-to-make-string-sorted/
// discuss: https://leetcode.com/problems/minimum-number-of-operations-to-make-string-sorted/discuss/?currentPage=1&orderBy=most_votes&query=
// submission codes start here
impl Solution {
pub fn make_string_sorted(s: String) -> i32 {
0
}
}
// submission codes end
#[cfg(test)]
mod tests {
use super::*;
#[test]
#[ignore]
fn test_1830_example_1() {
let s = "cba".to_string();
let result = 5;
assert_eq!(Solution::make_string_sorted(s), result);
}
#[test]
#[ignore]
fn test_1830_example_2() {
let s = "aabaa".to_string();
let result = 2;
assert_eq!(Solution::make_string_sorted(s), result);
}
}
// Accepted solution for LeetCode #1830: Minimum Number of Operations to Make String Sorted
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #1830: Minimum Number of Operations to Make String Sorted
// class Solution {
// private static final int N = 3010;
// private static final int MOD = (int) 1e9 + 7;
// private static final long[] f = new long[N];
// private static final long[] g = new long[N];
//
// static {
// f[0] = 1;
// g[0] = 1;
// for (int i = 1; i < N; ++i) {
// f[i] = f[i - 1] * i % MOD;
// g[i] = qmi(f[i], MOD - 2);
// }
// }
//
// public static long qmi(long a, int k) {
// long res = 1;
// while (k != 0) {
// if ((k & 1) == 1) {
// res = res * a % MOD;
// }
// k >>= 1;
// a = a * a % MOD;
// }
// return res;
// }
//
// public int makeStringSorted(String s) {
// int[] cnt = new int[26];
// int n = s.length();
// for (int i = 0; i < n; ++i) {
// ++cnt[s.charAt(i) - 'a'];
// }
// long ans = 0;
// for (int i = 0; i < n; ++i) {
// int m = 0;
// for (int j = s.charAt(i) - 'a' - 1; j >= 0; --j) {
// m += cnt[j];
// }
// long t = m * f[n - i - 1] % MOD;
// for (int v : cnt) {
// t = t * g[v] % MOD;
// }
// --cnt[s.charAt(i) - 'a'];
// ans = (ans + t + MOD) % MOD;
// }
// return (int) ans;
// }
// }
Use this to step through a reusable interview workflow for this problem.
For each element, scan the rest of the array looking for a match. Two nested loops give n × (n−1)/2 comparisons = O(n²). No extra space since we only use loop indices.
One pass through the input, performing O(1) hash map lookups and insertions at each step. The hash map may store up to n entries in the worst case. This is the classic space-for-time tradeoff: O(n) extra memory eliminates an inner loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.