2025-07-12：从盒子中找出字典序最大的字符串Ⅰ。用go语言，Alice 正在为她的 numFriends 个朋友准备一个游戏。游戏会进行多轮，每一轮中：
o 将字符串 word 分成 numFriends 个非空的子串，且分割方式不能与之前任何一轮的分割完全相同。
o 每一轮分割出来的所有子串都会被放进一个盒子里。
在所有轮次结束后，要求找出盒子中按字典序排列最大的字符串。
1 <= word.length <= 5 * 1000。
word 仅由小写英文字母组成。
1 <= numFriends <= word.length。
输入: word = "dbca", numFriends = 2。
输出: "dbc"。
解释:
所有可能的分割方式为：
"d" 和 "bca"。
"db" 和 "ca"。
"dbc" 和 "a"。
题目来自力扣3403。
解决思路
1. 理解分割方式：
o 将字符串 word 分成 numFriends 个非空子串，相当于在 word 中插入 numFriends - 1 个分隔符。
o 对于 numFriends = 2，分隔符可以插入的位置有 len(word) - 1 个（即 n-1 个位置）。
o 因此，所有可能的分割方式共有 C(n-1, numFriends-1) 种（组合数），但题目要求的分割方式不能重复。
2. 字典序最大的字符串：
o 我们需要在所有分割方式生成的所有子串中，找到字典序最大的子串。
o 字典序比较是从左到右逐个字符比较，第一个不同字符的 ASCII 码值决定了大小。
3. 关键观察：
o 字典序最大的子串一定是 word 的某个后缀（因为后缀可以尽可能保留更多的字符）。
o 但题目要求子串是分割后的结果，因此我们需要找到所有可能的分割方式中可能产生的最大子串。
o 实际上，最大的子串就是 word 的某个前缀或后缀，具体取决于分割方式。
4. 具体步骤：
o 首先，我们需要找到 word 的字典序最大的子串。根据题目描述，这个子串可以通过 lastSubstring 函数找到。
o lastSubstring 函数的作用是找到 word 的字典序最大的后缀（即从某个位置开始到末尾的子串）。
o 然后，我们需要考虑所有分割方式中可能产生的子串的最大值。由于分割方式不能重复，我们需要确保选取的子串尽可能长。
o 在 answerString 函数中，last 是 word 的字典序最大的后缀，然后根据 numFriends 的限制，截取 last 的前 min(m, n - numFriends + 1) 个字符。
5. 示例分析：
o word = "dbca", numFriends = 2：
o lastSubstring("dbca") 的结果是 "dbca"（因为 "dbca" 是最大的后缀）。
o n = 4, m = 4, n - numFriends + 1 = 3。
o min(4, 3) = 3，所以结果是 "dbc"。
时间复杂度
1. lastSubstring 函数：
o 使用双指针法，时间复杂度为 O(n)，其中 n 是 word 的长度。
o 最坏情况下，每个字符最多被比较两次（如 "aaaaa"），因此是线性时间。
2. answerString 函数：
o 调用 lastSubstring 和简单的截取操作，时间复杂度为 O(n)。
3. 总时间复杂度：O(n)。
空间复杂度
1. lastSubstring 和 answerString 函数：
o 只使用了常数级别的额外空间（如指针和临时变量）。
2. 总空间复杂度：O(1)。
总结
o 通过双指针法高效找到字典序最大的后缀。
o 根据 numFriends 的限制截取子串。
o 时间复杂度和空间复杂度均为最优。
Go完整代码如下：
.
package main
import (
"fmt"
)
func lastSubstring(s string)string {
i, j, n := 0, 1, len(s)
for j < n {
k := 0
for j+k < n && s[i+k] == s[j+k] {
k++
}
if j+k < n && s[i+k] < s[j+k] {
i, j = j, max(j+1, i+k+1)
} else {
j = j + k + 1
}
}
return s[i:]
}
func answerString(word string, numFriends int)string {
if numFriends == 1 {
return word
}
last := lastSubstring(word)
n, m := len(word), len(last)
return last[:min(m, n-numFriends+1)]
}
func main() {
word := "dbca"
numFriends := 2
result := answerString(word, numFriends)
fmt.Println(result)
}
Python完整代码如下：
.
# -*-coding:utf-8-*-
def last_substring(s: str) -> str:
i, j, n = 0, 1, len(s)
while j < n:
k = 0
while j + k < n and s[i + k] == s[j + k]:
k += 1
if j + k < n and s[i + k] < s[j + k]:
i, j = j, max(j + 1, i + k + 1)
else:
j = j + k + 1
return s[i:]
def answer_string(word: str, num_friends: int) -> str:
if num_friends == 1:
return word
last = last_substring(word)
n, m = len(word), len(last)
return last[:min(m, n - num_friends + 1)]
if __name__ == "__main__":
word = "dbca"
num_friends = 2
result = answer_string(word, num_friends)
print(result)·
我们相信Go语言和算法为普通开发者提供了困境的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。
欢迎关注“福大规模架构师每日一题”，让 Go 语言和算法助力您的职业发展
·