2026-03-14：反转后字典序最小的字符串。用go语言，给定一个只包含小写英文字母的字符串 s，长度为 n。 你必须恰好进行一次操作：选一个整数 k（1 ≤ k ≤ n），然后执行下面两者之一：

2026-03-14：反转后字典序最小的字符串。用go语言，给定一个只包含小写英文字母的字符串 s，长度为 n。

你必须恰好进行一次操作：选一个整数 k（1 ≤ k ≤ n），然后执行下面两者之一：

• 将 s 的前 k 个字符的顺序颠倒；或

• 将 s 的后 k 个字符的顺序颠倒。

要求在完成这一次操作后，使得到的字符串在字典序上尽可能小，并返回这个最小的结果。

这里的“字典序”按常规定义比较：从左到右找到第一个不同的字符，字母表中更靠前的字符对应的字符串更小；如果一串是另一串的前缀，则较短的那个更小。

1 <= n == s.length <= 1000。

s 由小写英文字母组成。

输入: s = “dcab”。

输出: “acdb”。

解释:

选择 k = 3，反转前 3 个字符。

将 “dca” 反转为 “acd”，得到的字符串 s = “acdb”，这是可获得的字典序最小的字符串。

题目来自力扣3722。

一、题目核心规则回顾

二、代码整体执行流程（分6大步骤）

步骤1：构造辅助字符串 t（核心预处理）

为了用后缀数组高效比较任意子串的字典序，代码先构造了一个特殊字符串t：

作用：把「原字符串的所有前缀、后缀」全部映射到t的后缀中，实现任意子串字典序的快速比较。

步骤2：生成后缀数组核心数据（SA、Rank、Height）

这一步是代码的核心工具，目的是实现O(1)时间比较任意两个子串的字典序，共生成3个数组：

步骤3：封装子串比较工具

基于上面的3个数据结构，代码封装了两个核心工具函数：

这是整个算法的效率核心：原本比较子串需要O(n)时间，现在变成O(1)时间。

步骤4：遍历所有「反转前k个字符」的方案（操作A）

这一步代码穷举所有k=1~n，逐个计算「反转前k个字符」后的字符串，找到其中最优的k值：

步骤5：遍历所有「反转后k个字符」的方案（操作B）

代码做了剪枝优化：只有当操作B的首字符 ≤ 操作A最优结果的首字符时，才需要计算（否则一定更差）。

步骤6：合并结果，返回最小值

对比操作A最优结果和操作B最优结果，选择字典序更小的那个返回。
示例中直接返回操作A的结果：acdb。

三、时间复杂度详细分析

核心计算逻辑：

总时间复杂度：

O(n log n)

解释：n是原字符串长度，n≤1000时效率极高；主导复杂度是稀疏表的O(n log n)，其余都是线性时间。

四、额外空间复杂度详细分析

额外空间=代码运行时除输入字符串外申请的所有内存：

总额外空间复杂度：

O(n log n)

解释：空间主要消耗在稀疏表上，整体与时间复杂度匹配，对于n≤1000完全无压力。

总结

Go完整代码如下：

package main

import (
"fmt"
"index/suffixarray"
"math/bits"
"slices"
"unsafe"
)

type sparseTable[T any] struct {
st [][]T
op func(T, T) T
}

func newSparseTable[T any](nums []T, op func(T, T) T) sparseTable[T] {
n := len(nums)
w := bits.Len(uint(n))
st := make([][]T, w)
for i := range st {
st[i] = make([]T, n)
}
copy(st[0], nums)
for i := 1; i < w; i++ {
for j := range n – 1<<i + 1 {
st[i][j] = op(st[i–1][j], st[i–1][j+1<<(i–1)])
}
}
return sparseTable[T]{st, op}
}

// [l, r) 下标从 0 开始
func (s sparseTable[T]) query(l, r int) T {
k := bits.Len(uint(r–l)) – 1
return s.op(s.st[k][l], s.st[k][r–1<<k])
}

func lexSmallest(s string) string {
n := len(s)
t := []byte(s)
slices.Reverse(t)
t = append(t, '#')
t = append(t, s…)

// === 后缀数组模板开始 ===

// 后缀数组 sa（后缀序）
// sa[i] 表示后缀字典序中的第 i 个字符串（的首字母）在 s 中的位置
// 特别地，后缀 s[sa[0]:] 字典序最小，后缀 s[sa[n-1]:] 字典序最大
sa := (*struct {
_ []byte
sa []int32
})(unsafe.Pointer(suffixarray.New(t))).sa

// 计算后缀名次数组
// 后缀 s[i:] 位于后缀字典序中的第 rank[i] 个
// 特别地，rank[0] 即 s 在后缀字典序中的排名，rank[n-1] 即 s[n-1:] 在字典序中的排名
// 相当于 sa 的反函数，即 rank[sa[i]] = i
rank := make([]int, len(sa))
for i, p := range sa {
rank[p] = i
}

// 计算高度数组（也叫 LCP 数组）
// height[0] = 0（哨兵）
// height[i] = LCP(s[sa[i]:], s[sa[i-1]:]) (i > 0)
height := make([]int, len(sa))
h := 0
// 计算 s 与 s[sa[rank[0]-1]:] 的 LCP（记作 LCP0）
// 计算 s[1:] 与 s[sa[rank[1]-1]:] 的 LCP（记作 LCP1）
// 计算 s[2:] 与 s[sa[rank[2]-1]:] 的 LCP
// …
// 计算 s[n-1:] 与 s[sa[rank[n-1]-1]:] 的 LCP
// 从 LCP0 到 LCP1，我们只去掉了 s[0] 和 s[sa[rank[0]-1]] 这两个字符
// 所以 LCP1 >= LCP0 – 1
// 这样就能加快 LCP 的计算了（类似滑动窗口）
// 注：实际只计算了 n-1 对 LCP，因为我们跳过了 rank[i] = 0 的情况
for i, rk := range rank {
if h > 0 {
h—
}
if rk > 0 {
for j := int(sa[rk–1]); i+h < len(t) && j+h < len(t) && t[i+h] == t[j+h]; h++ {
}
}
height[rk] = h
}

st := newSparseTable(height, func(a int, b int) int { return min(a, b) })
// 返回 LCP(s[i:], s[j:])，即两个后缀的最长公共前缀
lcp := func(i, j int) int {
if i == j {
return len(sa) – i
}
// 将 s[i:] 和 s[j:] 通过 rank 数组映射为 height 的下标
ri, rj := rank[i], rank[j]
if ri > rj {
ri, rj = rj, ri
}
// ri+1 是因为 height 的定义是 sa[i] 和 sa[i-1]
// rj+1 是因为 query 是左闭右开
return st.query(ri+1, rj+1)
}

// 比较两个子串，返回 strings.Compare(s[l1:r1], s[l2:r2])
compareSubstring := func(l1, r1, l2, r2 int) int {
len1, len2 := r1–l1, r2–l2
l := lcp(l1, l2)
if l >= min(len1, len2) {
// 一个是子串另一个子串的前缀，或者完全相等
return len1 – len2
}
// 此时两个子串一定不相等
return rank[l1] – rank[l2] // 也可以写 int(s[l1+l]) – int(s[l2+l])
}

// === 后缀数组模板结束 ===

// 反转前缀
ansK := 1
for k := 2; k <= n; k++ {
c := compareSubstring(n–k, n–k+ansK, n–ansK, n)
if c < 0 || c == 0 && compareSubstring(n–k+ansK, n, n+1+ansK, n+1+k) < 0 {
ansK = k
}
}
pre := []byte(s[:ansK])
slices.Reverse(pre)
ans := string(pre) + s[ansK:]

// 反转真后缀
// 剪枝：如果 s[0] > ans[0]，那么反转真后缀一定不优
if s[0] == ans[0] {
ansK = 1
for k := 2; k < n; k++ {
c := compareSubstring(0, k–ansK, n*2+1–k, n*2+1–ansK)
if c < 0 || c == 0 && compareSubstring(k–ansK, k, 0, ansK) < 0 {
ansK = k
}
}
suf := []byte(s[n–ansK:])
slices.Reverse(suf)
ans = min(ans, s[:n–ansK]+string(suf))
}
return ans
}

func main() {
s := "dcab"
result := lexSmallest(s)
fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

import math
from typing import List, Callable, Any

class SparseTable:
"""稀疏表，用于RMQ查询"""
def __init__(self, nums: List[Any], op: Callable[[Any, Any], Any]):
self.op = op
n = len(nums)
w = n.bit_length()
self.st = [[0] * n for _ in range(w)]

# 第0层：原数组
self.st[0] = nums[:]

# 构建稀疏表
for i in range(1, w):
length = 1 << i
for j in range(n – length + 1):
self.st[i][j] = op(self.st[i–1][j], self.st[i–1][j + (1 << (i–1))])

def query(self, l: int, r: int) –> Any:
"""查询[l, r)区间的最小值"""
k = (r – l).bit_length() – 1
return self.op(self.st[k][l], self.st[k][r – (1 << k)])

def build_suffix_array(s: str) –> List[int]:
"""
构建后缀数组（SA）
使用诱导排序(SA-IS)算法，复杂度O(n)
"""
n = len(s)
if n == 1:
return [0]

# 将字符转换为整数
s_int = [ord(c) for c in s]
max_val = max(s_int) + 1

# SA-IS算法实现
def sais(s_int: List[int], max_val: int) –> List[int]:
n = len(s_int)
if n == 0:
return []

# 类型数组：True表示L型，False表示S型
types = [False] * n
# 最后一个字符是S型
for i in range(n–2, –1, –1):
if s_int[i] < s_int[i+1]:
types[i] = False # S型
elif s_int[i] > s_int[i+1]:
types[i] = True # L型
else:
types[i] = types[i+1]

# 计算每个字符的桶大小
bucket_sizes = [0] * (max_val + 1)
for c in s_int:
bucket_sizes[c] += 1

# 计算每个桶的起始位置（累积和）
bucket_starts = [0] * (max_val + 1)
total = 0
for i in range(max_val + 1):
bucket_starts[i] = total
total += bucket_sizes[i]

# 初始化SA
sa = [–1] * n

# 第一步：放置所有LMS后缀
# 收集LMS位置
lms_positions = []
for i in range(1, n):
if not types[i] and types[i–1]:
lms_positions.append(i)

# 在桶的末尾放置LMS后缀
bucket_end = bucket_starts[:]
for i in range(len(bucket_end)):
bucket_end[i] += bucket_sizes[i] – 1

for i in range(len(lms_positions)–1, –1, –1):
pos = lms_positions[i]
c = s_int[pos]
sa[bucket_end[c]] = pos
bucket_end[c] -= 1

# 诱导排序L型
bucket_start = bucket_starts[:]
for i in range(n):
if sa[i] != –1 and sa[i] > 0 and types[sa[i]–1]:
c = s_int[sa[i]–1]
sa[bucket_start[c]] = sa[i] – 1
bucket_start[c] += 1

# 诱导排序S型
bucket_end = bucket_starts[:]
for i in range(len(bucket_end)):
bucket_end[i] += bucket_sizes[i] – 1

for i in range(n–1, –1, –1):
if sa[i] > 0 and not types[sa[i]–1]:
c = s_int[sa[i]–1]
sa[bucket_end[c]] = sa[i] – 1
bucket_end[c] -= 1

return sa

return sais(s_int, max_val)

def lex_smallest(s: str) –> str:
n = len(s)

# 构建扩展字符串：reversed(s) + '#' + s
t = s[::–1] + '#' + s

# 构建后缀数组
sa = build_suffix_array(t)

# 计算rank数组
rank = [0] * len(sa)
for i, p in enumerate(sa):
rank[p] = i

# 计算height数组（LCP）
height = [0] * len(sa)
h = 0
for i in range(len(t)):
if h > 0:
h -= 1
if rank[i] > 0:
j = sa[rank[i] – 1]
while i + h < len(t) and j + h < len(t) and t[i + h] == t[j + h]:
h += 1
height[rank[i]] = h

# 构建LCP查询的稀疏表
st = SparseTable(height, min)

def lcp(i: int, j: int) –> int:
"""计算两个后缀的最长公共前缀"""
if i == j:
return len(t) – i
ri, rj = rank[i], rank[j]
if ri > rj:
ri, rj = rj, ri
return st.query(ri + 1, rj + 1)

def compare_substring(l1: int, r1: int, l2: int, r2: int) –> int:
"""比较两个子串"""
len1, len2 = r1 – l1, r2 – l2
l = lcp(l1, l2)
if l >= min(len1, len2):
return len1 – len2
# 字符不同时，直接比较字符
return ord(t[l1 + l]) – ord(t[l2 + l])

# 反转前缀
ans_k = 1
for k in range(2, n + 1):
# 比较两种情况
c = compare_substring(n – k, n – k + ans_k, n – ans_k, n)
if c < 0 or (c == 0 and compare_substring(n – k + ans_k, n, n + 1 + ans_k, n + 1 + k) < 0):
ans_k = k

# 构造反转前缀的结果
prefix = s[:ans_k][::–1]
ans = prefix + s[ans_k:]

# 反转真后缀
if s[0] == ans[0]:
ans_k = 1
for k in range(2, n):
c = compare_substring(0, k – ans_k, n * 2 + 1 – k, n * 2 + 1 – ans_k)
if c < 0 or (c == 0 and compare_substring(k – ans_k, k, 0, ans_k) < 0):
ans_k = k

# 构造反转后缀的结果
suffix = s[n – ans_k:][::–1]
candidate = s[:n – ans_k] + suffix
ans = min(ans, candidate)

return ans

if __name__ == "__main__":
s = "dcab"
result = lex_smallest(s)
print(f"输入: {s}")
print(f"输出: {result}")

C++完整代码如下：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstring>
#include <cmath>

using namespace std;

// 稀疏表（Sparse Table）模板
template<typename T>
class SparseTable {
private:
vector<vector<T>> st;
function<T(T, T)> op;

public:
SparseTable(const vector<T>& nums, function<T(T, T)> opFunc) : op(opFunc) {
int n = nums.size();
if (n == 0) return;

int w = 32 – __builtin_clz(n); // bits.Len(uint(n))
st.resize(w, vector<T>(n));

for (int i = 0; i < n; i++) {
st[0][i] = nums[i];
}

for (int i = 1; i < w; i++) {
int step = 1 << (i – 1);
int limit = n – (1 << i);
for (int j = 0; j <= limit; j++) {
st[i][j] = op(st[i–1][j], st[i–1][j + step]);
}
}
}

// [l, r) 下标从 0 开始
T query(int l, int r) const {
int len = r – l;
int k = 31 – __builtin_clz(len); // bits.Len(uint(r-l)) – 1
return op(st[k][l], st[k][r – (1 << k)]);
}
};

// 计算后缀数组（倍增法）
vector<int> buildSuffixArray(const string& s) {
int n = s.length();
vector<int> sa(n);
vector<int> rank(n);
vector<int> tmp(n);

// 初始化排名
for (int i = 0; i < n; i++) {
rank[i] = s[i];
sa[i] = i;
}

// 倍增法构建后缀数组
for (int k = 1; k < n; k <<= 1) {
auto cmp = [&](int a, int b) {
if (rank[a] != rank[b]) return rank[a] < rank[b];
int ra = (a + k < n) ? rank[a + k] : –1;
int rb = (b + k < n) ? rank[b + k] : –1;
return ra < rb;
};

sort(sa.begin(), sa.end(), cmp);

tmp[sa[0]] = 0;
for (int i = 1; i < n; i++) {
tmp[sa[i]] = tmp[sa[i–1]] + (cmp(sa[i–1], sa[i]) ? 1 : 0);
}
rank = tmp;
}

return sa;
}

string lexSmallest(string s) {
int n = s.length();
if (n <= 1) return s;

string t = s;
reverse(t.begin(), t.end());
t += '#';
t += s;

// 构建后缀数组
vector<int> sa = buildSuffixArray(t);
int m = sa.size();

// 计算名次数组
vector<int> rank(m);
for (int i = 0; i < m; i++) {
rank[sa[i]] = i;
}

// 计算高度数组（LCP）
vector<int> height(m, 0);
int h = 0;
for (int i = 0; i < m; i++) {
if (h > 0) h—;
if (rank[i] > 0) {
int j = sa[rank[i] – 1];
while (i + h < m && j + h < m && t[i + h] == t[j + h]) {
h++;
}
}
height[rank[i]] = h;
}

// 构建 LCP 的稀疏表
SparseTable<int> st(height, [](int a, int b) { return min(a, b); });

// 返回 LCP(s[i:], s[j:])
function<int(int, int)> lcp = [&](int i, int j) -> int {
if (i == j) return m – i;
int ri = rank[i], rj = rank[j];
if (ri > rj) swap(ri, rj);
return st.query(ri + 1, rj + 1);
};

// 比较两个子串
function<int(int, int, int, int)> compareSubstring = [&](int l1, int r1, int l2, int r2) -> int {
int len1 = r1 – l1;
int len2 = r2 – l2;
int l = lcp(l1, l2);
if (l >= min(len1, len2)) {
return len1 – len2;
}
return rank[l1] – rank[l2];
};

// 反转前缀
int ansK = 1;
for (int k = 2; k <= n; k++) {
int c = compareSubstring(n – k, n – k + ansK, n – ansK, n);
if (c < 0 || (c == 0 && compareSubstring(n – k + ansK, n, n + 1 + ansK, n + 1 + k) < 0)) {
ansK = k;
}
}

string pre = s.substr(0, ansK);
reverse(pre.begin(), pre.end());
string ans = pre + s.substr(ansK);

// 反转真后缀
if (s[0] == ans[0]) {
ansK = 1;
for (int k = 2; k < n; k++) {
int c = compareSubstring(0, k – ansK, n * 2 + 1 – k, n * 2 + 1 – ansK);
if (c < 0 || (c == 0 && compareSubstring(k – ansK, k, 0, ansK) < 0)) {
ansK = k;
}
}
string suf = s.substr(n – ansK, ansK);
reverse(suf.begin(), suf.end());
string candidate = s.substr(0, n – ansK) + suf;
if (candidate < ans) {
ans = candidate;
}
}

return ans;
}

int main() {
string s = "dcab";
string result = lexSmallest(s);
cout << result << endl;
return 0;
}