题目描述

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

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

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

在所有回合结束后，找出盒子中 字典序最大的 字符串。

字符串 a 的字典序 小于 字符串 b 的前提是：在两个字符串上第一处不同的位置上，a 的字母在字母表中的顺序早于 b 中对应的字母。
如果前 min(a.length, b.length) 个字符都相同，那么较短的字符串字典序更小。

样例

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

输出："dbc"

解释：

所有可能的分割方式为：

"d" 和 "bca"。
"db" 和 "ca"。
"dbc" 和 "a"。

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

输出："g"

解释：

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

限制

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

算法

(最大表示法) $O(n)$

1. 暴力的做法是枚举所有位置开头的子串，并找到长度最多为 $n-numFriends+1$ 字典序最大的子串。
2. 借鉴最大（小）表示法的策略，在比较以 $i$ 开头和以 $j$ 开头的子串时，假设第 $k$ 个字符发生了不一致。如果 $s(i + k) < s(j + k)$，则 $i$ 到 $i + k$ 开头的子串都是不优的（$i + p$ 开头的子串一定比 $j + p$ 开头的子串差。
3. 初始时选中 $i = 0$ 和 $j = 1$ 做比较，途中保持 $i$ 永远是最优的。
4. 注意当 numFriends=1 时直接返回原串。

时间复杂度

• 最大表示法的时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    string answerString(string word, int numFriends) {
        if (numFriends == 1)
            return word;

        const int n = word.size();
        int i = 0, j = 1;

        while (j < n) {
            int k = 0;
            while (k < numFriends && i + k < n && j + k < n) {
                if (word[i + k] != word[j + k])
                    break;

                ++k;
            }

            if (k < numFriends && j + k < n && word[i + k] < word[j + k])
                i = i + k + 1;
            else
                j = j + k + 1;

            if (i > j)
                swap(i, j);

            if (i == j)
                ++j;
        }

        return word.substr(i, n - numFriends + 1);
    }
};