冷门但有用的算法知识 - 字符串的最小(大)表示法

lucifer

2025-01-18

字数统计: 2.1k字 | 阅读时长≈ 8分

今天来给大家介绍一种冷门但有用的算法知识——字符串的最小(大)表示法。尽管它是一种冷门算法，但是它确是一种母题。也就是说很多题目根据它换个皮就变成了一道新的题目。因此掌握它就可以掌握一整类题目。

什么是字符串的最小(大)表示法

首先我们来认识一下什么是最小表示法和最大表示法。由于字符串的最小表示法和最大表示法是类似的，因此本文仅以最小表示法为例进行介绍。

用一句话来进行描述：“字符串的最小表示法就是对一个字符串 s ，求 s 的循环的同构字符串 s’ 中字典序最小的一个。”

比如：s = bacd，则循环的同构字符串 s’ 可以是 acdb,cdba,dbac，其中最小表示的 s’ 是acdb。即该字符串的循环同构字符串中字典序最小的一个是 acdb，也就是 s 的最小表示法就是 acdb。

算法概述

我们使用两个指针： i 和 j，其中 i 指向截止到目前最小表示的位置（备胎），j 指向下一个待比较指针。对于 i 和 j，我们逐个比较其字符的字典序大小，并根据字典序大小来移动指针。下面是具体步骤：

初始化 i = 0,j = 1
若s[i] > s[j], 则当前 i 指向的位置一定不是最小表示的起点位置，修改 i 的值，i = i + 1，j = j’，其中 j’ 是上一次 i 和 j 指向相同字符的位置（步骤四的情况）。
若s[i] < s[j], 则当前 j 指向的位置一定不是最小表示的起点位置，修改 j 的值，j = j + 1，i = i’，其中 i’ 是上一次 i 和 j 指向相同字符的位置（步骤四的情况）。
若s[i] = s[j], 无法确定以 i 开头的和以 j 开头的哪个更小。因此我们继续比较，更新指针 i = i + 1, j = j + 1并继续判断，直到 s[i] != s[j]，这时转到步骤2 或者步骤 3（当然也可以退出算法）。
不断执行步骤 2 到 4，直到 i 或者 j 指向字符串末尾。最后返回 i 所指向的位置，即为最小表示法的起始位置。

由于 i 和 j 在步骤2 和步骤 3 可能会回退其中 i 或者 j。因此代码实现时，我们可以用第三个变量 k 来记录当前比较后已经相等的字符数量。这样不更新就是回退，更新 i = i + k + 1 就是更新 i 的位置，更新 j = j + k + 1 就是更新 j 的位置。具体见下方代码。

代码

k, i, j = 0, 0, 1
while k < n and i < n and j < n:
    if s[(i + k) % n] == s[j + k]) % n]:
        k += 1
    else:
        if s[(i + k) % n] > s[(j + k) % n]:
            i = i + k + 1
        else:
            j = j + k + 1
        if i >= j:
            j = i + 1
        k = 0
print(i)

复杂度分析

算法的关键点就是步骤 2 和 3，跳过了很多无用的比较，优化了比较的时间复杂度。如果是暴力比较，那么需要 O(n^2) 的时间复杂度。虽然指针 i 和 j 可能会回退，但是回退只会回退其中一个，而不可能两个同时回退，而 i 或者 j 到达字符串结尾都会导致算法退出，因此总的时间复杂度是 $O(n)$，其中 n 为 s 的长度。

我们来进一步分析一下步骤 2 和 3的精髓。由于步骤 2 和 3 只是不同情况，逻辑是类似的，因此只以步骤 2 为例来分析。

比如 s = bbz....bbc，其中 i 指向第一个 b，j 指向第三个 b。由于他俩相同，因此更新 i 到第二个 b 的位置，j 指向第四个 b。由于他俩还是相同，因此继续更新 i 指向 z，j 指向 c。

此时 z > c，刚好就是算法的第二个步骤。这种情况下对于任何以括号里的字符开头的 (bbz）....bbc 这些字符串，都不可能是最小的。因为我们总能找到一个比他更小的字符串。

具体来说：

任何以第一个 b 开头的字符串都不可能比以第三个 b 开头的字符串小
任何以第二个 b 开头的字符串都不可能比以第四个 b 开头的字符串小
任何以 z 开头的字符串都不可能比以 c 开头的字符串小

因此直接更新 i 指向 z 的后一个指针即可。

应用

我们来通过两道力扣的题目来看看字符串的最小表示法的应用。相信如果你理解了这个算法，一定可以秒解这两道题目。

1163. 按字典序排在最后的子串

给你一个字符串 s ，找出它的所有子串并按字典序排列，返回排在最后的那个子串。


示例 1：

输入：s = "abab"
输出："bab"
解释：我们可以找出 7 个子串 ["a", "ab", "aba", "abab", "b", "ba", "bab"]。按字典序排在最后的子串是 "bab"。
示例 2：

输入：s = "leetcode"
输出："tcode"
 

提示：

1 <= s.length <= 4 * 105
s 仅含有小写英文字符。

这道题几乎没有伪装，就是求字典序最大的子串。但是更简单，因为不需要考虑循环同构字符串的问题。

代码参考：

class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, k = 0, 1, 0
        while j + k < len(s):
            if s[i + k] == s[j + k]:
                k += 1
            elif s[i + k] < s[j + k]:
                i += k + 1
                k = 0
                if i >= j:
                    j = i + 1
            else:
                j += k + 1
                k = 0
        return s[i:]

3403. 从盒子中找出字典序最大的字符串 I

给你一个字符串 word 和一个整数 numFriends。

Alice 正在为她的 numFriends 位朋友组织一个游戏。游戏分为多个回合，在每一回合中：

word 被分割成 numFriends 个 非空 字符串，且该分割方式与之前的任意回合所采用的都 不完全相同 。
所有分割出的字符串都会被放入一个盒子中。
在所有回合结束后，找出盒子中 
字典序最大的 
字符串。

 

示例 1：

输入: word = "dbca", numFriends = 2

输出: "dbc"

解释: 

所有可能的分割方式为：

"d" 和 "bca"。
"db" 和 "ca"。
"dbc" 和 "a"。
示例 2：

输入: word = "gggg", numFriends = 4

输出: "g"

解释: 

唯一可能的分割方式为："g", "g", "g", 和 "g"。

 

提示:

1 <= word.length <= 5 * 103
word 仅由小写英文字母组成。
1 <= numFriends <= word.length

这道题就是求字典序最大的字符串，但是多了一个长度限制。由于分割为 k 个非空字符串，k - 1 个字符串最少是 k - 1 的长度，因此字典序最大的字符串长度不能超过 (n - (k - 1)) 也就是 n-k+1。

由于字符串越长字典序越大，因此我们直接取长度为 n - k + 1 的字符串即可。但是由于这道题仍然不能考虑循环同构字符串的问题，也就是说可能取不到 n - k + 1 长度的字符串（可能比 n - k + 1 短）。这个不难，我们求出来后直接截取前 n - k + 1 个字符即可。

代码直接复用上一题的代码。

class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, k = 0, 1, 0
        while j + k < len(s):
            if s[i + k] == s[j + k]:
                k += 1
            elif s[i + k] < s[j + k]:
                i += k + 1
                k = 0
                if i >= j:
                    j = i + 1
            else:
                j += k + 1
                k = 0
        return s[i:]
    def answerString(self, s: str, k: int) -> str:
        if k == 1:
            return s
        n = len(s)
        return self.lastSubstring(s)[:n-k+1]

总结

字符串的最小表示法是一种非常有用的算法，它可以帮助我们解决很多字符串字典序最小问题。知晓了这个算法，将来看到别的题目可能就能够识别到这是一道换皮题，进而通过本文的算法来解决。这也是总结母题的意义所在。