2023-05-27：给你一个只包含小写英文字母的字符串 s 。
(相关资料图)
每一次 操作 ，你可以选择 s 中两个 相邻 的字符，并将它们交换。
请你返回将 s 变成回文串的 最少操作次数 。
注意 ，输入数据会确保 s 一定能变成一个回文串。
输入：s = "letelt"。
输出：2。
答案2023-05-27：
大体过程如下：1.定义结构体 IndexTree，其中包含一个整型切片 tree和整型变量 n，用于实现树状数组。
2.定义函数 createIndexTree(size int) *IndexTree，用于创建一个大小为 size的树状数组并初始化，返回该数组的指针。
3.定义函数 sum(it *IndexTree, i int) int，用于求以 i为结尾的前缀和。
4.定义函数 add(it *IndexTree, i int, v int)，用于将第 i个位置上的值增加 v。
5.定义函数 merge(arr []int, help []int, l int, m int, r int) int，用于归并排序并统计逆序对数量。
6.定义函数 number(arr []int, help []int, l int, r int) int，用于递归地求解整个序列中的逆序对数量。
7.定义函数 minMovesToMakePalindrome(s string) int，用于求解将字符串 s变成回文串的最少操作次数。首先遍历字符串，将每个字符第一次出现的下标加入到对应字符的索引列表中。然后定义一个整型切片 arr用于记录每个字符与其对称位置之间的距离，以及一个 IndexTree类型的变量 it用于记录每个字符在左半部分的逆序对数量。遍历整个字符串，对于每个未处理的位置，找到它与其对称位置之间的距离，并计算出在左半部分有多少个字符与该字符构成了逆序对。最后调用 number函数求解 arr中的逆序对数量即可。
8.在 main函数中定义字符串 s = "letelt"，并调用 minMovesToMakePalindrome函数输出结果。
时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。
其中，遍历整个字符串的时间复杂度为 $O(n)$，建立字符索引列表的时间复杂度为 $O(n)$，建立树状数组的时间复杂度为 $O(n\log n)$，递归求解逆序对数量的时间复杂度为 $O(n\log n)$，归并排序中合并两个有序子序列的时间复杂度为 $O(n)$。
而空间复杂度中，建立字符索引列表占用的空间为 $O(26n)$，建立树状数组占用的空间为 $O(n\log n)$，递归求解逆序对数量时传递的辅助数组占用的空间为 $O(n)$。
go语言完整代码如下：package mainimport "fmt"func main() {s := "letelt"result := minMovesToMakePalindrome(s)fmt.Println(result)}func minMovesToMakePalindrome(s string) int {n := len(s)indies := make([][]int, 26)for i := 0; i < 26; i++ {indies[i] = []int{}}for i := 0; i < n; i++ {c := int(s[i]) - "a"indies[c] = append(indies[c], i+1)}arr := make([]int, n+1)it := newIndexTree(n)for i, l := 0, 1; i < n; i, l = i+1, l+1 {if arr[l] == 0 {c := int(s[i]) - "a"r := indies[c][len(indies[c])-1]indies[c] = indies[c][:len(indies[c])-1]if l == r {arr[l] = (1 + n) / 2it.add(l, -1)} else {kth := it.sum(l)arr[l] = ktharr[r] = n - kth + 1it.add(r, -1)}}}return number(arr, make([]int, n+1), 1, n)}type indexTree struct {tree []intn int}func newIndexTree(size int) *indexTree {tree := make([]int, size+1)ans := &indexTree{tree: tree, n: size}for i := 1; i <= size; i++ {ans.add(i, 1)}return ans}func (it *indexTree) sum(i int) int {ans := 0for i > 0 {ans += it.tree[i]i -= i & -i}return ans}func (it *indexTree) add(i int, v int) {for i < len(it.tree) {it.tree[i] += vi += i & -i}}func number(arr []int, help []int, l int, r int) int {if l >= r {return 0}mid := l + ((r - l) >> 1)return number(arr, help, l, mid) + number(arr, help, mid+1, r) + merge(arr, help, l, mid, r)}func merge(arr []int, help []int, l int, m int, r int) int {i := rp1 := mp2 := rans := 0for p1 >= l && p2 > m {if arr[p1] > arr[p2] {ans += p2 - mhelp[i] = arr[p1]i--p1--} else {help[i] = arr[p2]i--p2--}}for p1 >= l {help[i] = arr[p1]i--p1--}for p2 > m {help[i] = arr[p2]i--p2--}for i := l; i <= r; i++ {arr[i] = help[i]}return ans}fn main() { let s = String::from("letelt"); let result = min_moves_to_make_palindrome(s); println!("{}", result);}fn min_moves_to_make_palindrome(s: String) -> i32 { let n = s.len(); let mut indies: Vec> = vec![vec![]; 26]; for (i, c) in s.chars().enumerate() { let index = (c as u8 - b"a") as usize; indies[index].push((i + 1) as i32); } let mut arr: Vec = vec![0; n as usize + 1]; let mut it = IndexTree::new(n as i32); let mut i = 0; let mut l = 1; while i < n { if arr[l as usize] == 0 { let c_index = (s.chars().nth(i as usize).unwrap() as u8 - b"a") as usize; let a = indies[c_index].len() - 1; let r = indies[c_index][a]; indies[c_index].remove(a); if l == r { arr[l as usize] = (1 + n as i32) / 2; it.add(l, -1); } else { let kth = it.sum(l); arr[l as usize] = kth; arr[r as usize] = n as i32 - kth + 1; it.add(r, -1); } } i += 1; l += 1; } number(&mut arr, &mut vec![0; n as usize + 1], 1, n as i32)}struct IndexTree { tree: Vec, n: i32,}impl IndexTree { fn new(size: i32) -> Self { let tree = vec![0; size as usize + 1]; let mut ans = Self { tree, n: size }; for i in 1..=size { ans.add(i, 1); } return ans; } fn sum(&self, mut i: i32) -> i32 { let mut ans = 0; while i > 0 { ans += self.tree[i as usize]; i -= i & -i; } ans } fn add(&mut self, mut i: i32, v: i32) { while i < self.tree.len() as i32 { self.tree[i as usize] += v; i += i & -i; } }}fn number(arr: &mut Vec, help: &mut Vec, l: i32, r: i32) -> i32 { if l >= r { return 0; } let mid = l + ((r - l) >> 1); return number(arr, help, l, mid) + number(arr, help, mid + 1, r) + merge(arr, help, l, mid, r);}fn merge(arr: &mut Vec, help: &mut Vec, l: i32, m: i32, r: i32) -> i32 { let mut i = r; let mut p1 = m; let mut p2 = r; let mut ans = 0; while p1 >= l && p2 > m { ans += if arr[p1 as usize] > arr[p2 as usize] { p2 - m } else { 0 }; if arr[p1 as usize] > arr[p2 as usize] { help[i as usize] = arr[p1 as usize]; p1 -= 1; } else { help[i as usize] = arr[p2 as usize]; p2 -= 1; }; i -= 1; } while p1 >= l { help[i as usize] = arr[p1 as usize]; i -= 1; p1 -= 1; } while p2 > m { help[i as usize] = arr[p2 as usize]; i -= 1; p2 -= 1; } for i in l..=r { arr[i as usize] = help[i as usize]; } ans} #include #include using namespace std;struct IndexTree { vector tree; int n; IndexTree(int size) { tree.resize(size + 1); n = size; for (int i = 1; i <= n; i++) { add(i, 1); } } int sum(int i) { int ans = 0; while (i > 0) { ans += tree[i]; i -= i & -i; } return ans; } void add(int i, int v) { while (i < tree.size()) { tree[i] += v; i += i & -i; } }};int merge(vector& arr, vector& help, int l, int m, int r);int number(vector& arr, vector& help, int l, int r) { if (l >= r) { return 0; } int mid = l + ((r - l) >> 1); return number(arr, help, l, mid) + number(arr, help, mid + 1, r) + merge(arr, help, l, mid, r);}int merge(vector& arr, vector& help, int l, int m, int r) { int i = r; int p1 = m; int p2 = r; int ans = 0; while (p1 >= l && p2 > m) { if (arr[p1] > arr[p2]) { ans += p2 - m; help[i--] = arr[p1--]; } else { help[i--] = arr[p2--]; } } while (p1 >= l) { help[i--] = arr[p1--]; } while (p2 > m) { help[i--] = arr[p2--]; } for (i = l; i <= r; i++) { arr[i] = help[i]; } return ans;}int minMovesToMakePalindrome(char* s) { int n = strlen(s); vector> indies(26, vector()); for (int i = 0, j = 1; i < n; i++, j++) { int c = s[i] - "a"; indies[c].push_back(j); } vector arr(n + 1, 0); IndexTree it(n); for (int i = 0, l = 1; i < n; i++, l++) { if (arr[l] == 0) { int c = s[i] - "a"; int r = indies[c].back(); indies[c].pop_back(); if (l == r) { arr[l] = (1 + n) / 2; it.add(l, -1); } else { int kth = it.sum(l); arr[l] = kth; arr[r] = n - kth + 1; it.add(r, -1); } } } vector help(n + 1, 0); int ans = number(arr, help, 1, n); return ans;}int main() { char s[] = "letelt"; int result = minMovesToMakePalindrome(s); cout << result << endl; return 0;}