如何在O(n)时间复杂度内找出字符串的所有循环排列？

嘿，这个问题抓得很准！你已经发现了原解法的核心性能问题——每次insert和erase都会挪动整个字符串的字符，导致看似简单的循环背后藏着O(n²)的时间开销，还因为内存移动的常数太大导致超时。咱们来拆解一下这个问题，看看怎么优化：

如果你的需求是生成并存储所有n个循环排列的完整字符串，那么总时间复杂度不可能低于O(n²)——因为最终需要生成的总字符数是n×n = n²个，这是理论下界。你原来的解法超时，不是因为时间复杂度的阶，而是因为insert和erase操作的常数开销太大。

我们可以换一种方式构造循环排列，完全避免频繁的内存移动操作：

方案1：直接通过索引映射构造每个排列 #

这种方式不需要修改原字符串，直接根据偏移量计算每个字符的位置，逐个赋值构造新字符串。以C++为例：

vector<string> permu;
int n = str.size();
permu.reserve(n); // 预先分配空间，避免多次扩容带来的开销
for(int start = 0; start < n; start++){
    string s(n, ' ');
    for(int k = 0; k < n; k++){
        // 计算当前字符在原字符串中的索引
        s[k] = str[(start + k) % n];
    }
    permu.push_back(s);
}

这里没有任何字符串的插入/删除操作，每个字符都是直接赋值，内存操作的常数项比原解法小很多，在大多数场景下都能解决超时问题。

方案2：利用字符串拼接+子串截取（适合Python等语言） #

如果是Python这类字符串切片效率极高的语言，可以把原字符串和自身拼接，然后直接截取长度为n的子串——所有循环排列其实就是拼接字符串中连续的n长度子串：

original = "abcd"
doubled = original + original
permutations = [doubled[i:i+len(original)] for i in range(len(original))]

Python的字符串切片会共享底层的字符数组，所以这个操作的实际开销非常低，虽然理论时间复杂度还是O(n²)，但实际运行速度会比手动循环快很多。

如果你的需求只是遍历每个循环排列的字符，而不需要把每个排列都保存成独立的字符串，那可以做到O(1)额外空间（除了原字符串）：

int n = str.size();
for(int start = 0; start < n; start++){
    // 遍历当前循环排列的所有字符
    for(int k = 0; k < n; k++){
        char c = str[(start + k) % n];
        // 在这里处理字符c，比如输出或计算
    }
}

这种方式完全没有字符串拷贝，所有访问都是O(1)的数组索引，虽然总操作数还是O(n²)，但内存开销降到了最低。

内容的提问来源于stack exchange，提问作者UTL