字符串的循环同构与最小表示法

摘要: 循环同构字符串中哪个字典序最小

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

问题背景

给定一个字符串 s，如果不断把最后一个字符放在开头，最终会得到 $n$ 个字符串，称这 $n$ 个字符串是循环同构的。其中字典序最小的一个，称为字符串 s 的最小表示。

记 $B[i]$ 表示 $S$ 中以 $i$ 开头的循环同构字符串。这样最小表示法用开始字符的下标即可表示。

下面我们来看一下如何求一个字符串的最小表示。之后以一个模板题来给出代码模板，最后在代码模板的基础上，解决 899. 有序队列。

算法

暴力

最暴力的做法是按照定义比较 $n$ 个循环同构字符串。

比较循环同构字符串 $B[i]$ 与 $B[j]$ 时，枚举 $k = 0, 1, \cdots, n-1$，比较 $s[(i + k) \% n]$ 与 $s[(j + k) \% n]$，直至找到一个不相等的位置，从而确定 $B[i]$ 与 $B[j]$ 的大小关系。

剪枝

由于我们要找的是最小表示法，所以如果能够确定某些位置肯定不是最小表示的时候，即可在对比 $B[i], B[j]$ 时跳过这些下标。

考虑 $B[i], B[j]$ 的对比过程，假设在对比到 $s[(i + k) \% n]$ 和 $s[(j + k) \% n]$ 时发生不同，不妨设 $s[(i + k) \% n]$ < $s[(j + k) \% n]$。因此 $B[j]$ 肯定不是最小表示法。

此外，我们还可以知道 $B[(j+1)\%n], B[(j+2)\%n], \cdots, B[(j+k)\%n]$ 肯定不是最小表示。，因为对于 $1 \leq p \leq k$，$B[(i+1)\%n]$ 肯定比 $B[(j+1)\%n]$ 更小。于是在暴力法中，下一步应该对比 $B[i\% n]$ 与 $B[(j + 1)\% n]$，现在可以直接对比 $B[i]$ 与 $B[(j + k + 1)\% n]$ 了。当然这里还有一些细节需要注意，完整算法如下：

对比过程从 $i = 0, j = 1$ 开始，根据对比结果，推进 $i$ 或 $j$，推进过程始终保持 $i \neq j$。考虑 $B[i]$，$B[j]$ 的对比结果。

• 如果扫描了 $n$ 个仍然相等，则说明 $S$ 中有循环节，此时 $B[\min(i, j)]$ 为最小表示法。
• 如果在 $s[(i+k)\% n]$ 与 $s[(j+k)\% n]$ 发现不同：
  • 若 $s[(i+k)\% n] < s[(j+k)\% n]$，则置 $j = j + k + 1$，若此时 $i = j$，则再置 $j = j + 1$。
  • 若 $s[(i+k)\% n] > s[(j+k)\% n]$，则置 $i = i + k + 1$，若此时 $i = j$，则再置 $i = i + 1$。

重复以上循环，直至 $i$ 或 $j$ 回到了 $0$。

下面以一个模板题看一下该算法的实现。

模板题: P1368 【模板】最小表示法

给定数组 A，每步操作可以把数组最左边元素放到最右边。

对 A 执行任意次操作后，返回可以取到的字典序最小的数组。

输入格式
第一行一个整数 n，代表方块的数目。
第二行  n 个整数，每个整数按从左到右的顺序输出方块瑕疵度的值。

输出格式
一行 n 个整数，代表最美观工艺品从左到右瑕疵度的值。

数据范围
n <= 3e5

输入输出样例
输入
10
10 9 8 7 6 5 4 3 2 1
输出
1 10 9 8 7 6 5 4 3 2

代码 (C++，模板)

#include <iostream>
#include <vector>

using namespace std;

int get_min_representation(const vector<int>& s)
{
    int N = s.size();
    int i = 0, j = 1;
    while(i < N && j < N)
    {
        int k = 0;
        while(k < N && s[(i + k) % N] == s[(j + k) % N])
            k++;
        if(k == N)
            break;
        if(s[(i + k) % N] < s[(j + k) % N])
        {
            j += k + 1;
            if(i == j)
                j++;
        }
        else
        {
            i += k + 1;
            if(i == j)
                i++;
        }
    }
    return min(i, j);
}

int main()
{
    int N;
    cin >> N;
    vector<int> s(N);
    for(int i = 0; i < N; ++i)
        cin >> s[i];

    int ans = get_min_representation(s);
    for(int k = 0; k < N; ++k)
        cout << s[(ans + k) % N] << " ";
    cout << endl;
}

代码 (Python，模板)

from typing import List

def get_min_representation(s: List[int]) -> int:
    N = len(s)
    i = 0
    j = 1
    while i < N and j < N:
        k = 0
        while k < N and s[(i + k) % N] == s[(j + k) % N]:
            k += 1
        if k == N:
            break
        if s[(i + k) % N] < s[(j + k) % N]:
            j += k + 1
            if i == j:
                j += 1
        else:
            i += k + 1
            if i == j:
                i += 1
    return min(i, j)

def main():
    N = int(input())
    s = [int(x) for x in input().split()]
    ans = get_min_representation(s)

    for k in range(N):
        print("{} ".format(s[(ans + k) % N]), end="")


if __name__ == "__main__":
    main()

899. 有序队列

给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个，并把它加到字符串的末尾。

返回 在应用上述步骤的任意数量的移动后，字典序最小的字符串 。

提示：

1 <= k <= S.length <= 1000
s 只由小写字母组成。

示例 1：
输入：s = “cba”, k = 1
输出：”acb”
解释：
在第一步中，我们将第一个字符（“c”）移动到最后，获得字符串 “bac”。
在第二步中，我们将第一个字符（“b”）移动到最后，获得最终结果 “acb”。

示例 2：
输入：s = “baaca”, k = 3
输出：”aaabc”
解释：
在第一步中，我们将第一个字符（“b”）移动到最后，获得字符串 “aacab”。
在第二步中，我们将第三个字符（“c”）移动到最后，获得最终结果 “aaabc”。

算法：最小表示法

当 $k = 1$ 时，即为循环同构字符串取字典序最小的问题，用最小表示法即可解决。

当 $k > 1$ 时，字符串中的字符可以取到任意顺序，因此将字符串中的字符排序即可。下面说明 $k > 1$ 时字符可以取到任意顺序的正确性。

引理1 (冒泡排序的正确性)

进行有限次交换相邻元素的操作，可以将一个数组从小到大排序。

---

证明(数学归纳法)

对数组长度 $n$ 用数学归纳法。

当 $n = 1$ 时，数组有序，结论正确。

假设 $n=k-1$ 时，结论正确，也就是可以将一个长为 $k-1$ 的数组经过有限次交换相邻元素操作使其有序。

下面考虑 $n=k$ 的情况。对于长为 $k$ 的数组，经过一趟冒泡，数组的最小值会交换到数组的第一个位置，还剩第 2 到第 $k$ 个元素，这部分的长度为 $k-1$，由归纳假设，可以经过有限次交换相邻元素操作使其有序。因此 $n=k$ 的结论成立。

$\Box$

引理2

当 $k > 1$ 时，可以完成交换任意相邻元素的操作。

---

证明(构造性证明)

不妨设要交换的相邻元素为 $ch1 = s[i], ch2 = s[i+1]$，$0 \leq i < n-1$。

首先不断将 $s[0]$ 移动到末尾，直至 $ch1$ 移动到 $s[0]$，此时 $ch2$ 自然在 $s[1]$ 位置。

然后将 $s[1]$ 移动到末尾，然后将 $s[0]$ 移动到末尾，此时 $ch1$ 和 $ch2$ 完成交换。

然后继续不断将 $s[0]$ 移动到末尾，直至交换后的 $ch2$ 移动到原 $s[i]$ 的位置，此时 $ch1$ 自然在 $s[i+1]$ 的位置。

这样原串 $s$ 中的 $s[i]$ 和 $s[i+1]$ 即完成交换，同时其它部分保持不变。

$\Box$

由以上引理2，当 $k > 1$ 时，$s$ 可以完成交换任意相邻元素的操作。再由引理1，$s$ 中的字符可以排序为从小到大的顺序。

代码 (Python)

def get_min_representation(s: List[int]) -> int:
    N = len(s)
    i = 0
    j = 1
    while i < N and j < N:
        k = 0
        while k < N and s[(i + k) % N] == s[(j + k) % N]:
            k += 1
        if k == N:
            break
        if s[(i + k) % N] < s[(j + k) % N]:
            j += k + 1
            if i == j:
                j += 1
        else:
            i += k + 1
            if i == j:
                i += 1
    return min(i, j)

class Solution:
    def orderlyQueue(self, s: str, k: int) -> str:
        n = len(s)
        if k == 1:
            ans = get_min_representation(s)
            result = []
            for k in range(n):
                result.append(s[(ans + k) % n])
            return "".join(result)
        result = list(s)
        result.sort()
        return "".join(result)

---