2025-07-12：从盒子中找出字典序最大的字符串Ⅰ。用go语言，Alice 正在为她的 numFriends 个朋友准备一个

2025-07-12：从盒子中找出字典序最大的字符串Ⅰ。用go语言，Alice 正在为她的 numFriends 个朋友准备一个游戏。游戏会进行多轮，每一轮中：

• • 将字符串 word 分成 numFriends 个非空的子串，且分割方式不能与之前任何一轮的分割完全相同。
• • 每一轮分割出来的所有子串都会被放进一个盒子里。

在所有轮次结束后，要求找出盒子中按字典序排列最大的字符串。

1 <= word.length <= 5 * 1000。

word 仅由小写英文字母组成。

1 <= numFriends <= word.length。

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

输出: "dbc"。

解释:

所有可能的分割方式为：

"d" 和 "bca"。

"db" 和 "ca"。

"dbc" 和 "a"。

题目来自力扣3403。

解决思路

1. 1. 理解分割方式：
   • • 将字符串 word 分成 numFriends 个非空子串，相当于在 word 中插入 numFriends - 1 个分隔符。
   • • 对于 numFriends = 2，分隔符可以插入的位置有 len(word) - 1 个（即 n-1 个位置）。
   • • 因此，所有可能的分割方式共有 C(n-1, numFriends-1) 种（组合数），但题目要求的分割方式不能重复。
2. 2. 字典序最大的字符串：
   • • 我们需要在所有分割方式生成的所有子串中，找到字典序最大的子串。
   • • 字典序比较是从左到右逐个字符比较，第一个不同字符的 ASCII 码值决定了大小。
3. 3. 关键观察：
   • • 字典序最大的子串一定是 word 的某个后缀（因为后缀可以尽可能保留更多的字符）。
   • • 但题目要求子串是分割后的结果，因此我们需要找到所有可能的分割方式中可能产生的最大子串。
   • • 实际上，最大的子串就是 word 的某个前缀或后缀，具体取决于分割方式。
4. 4. 具体步骤：
   • • 首先，我们需要找到 word 的字典序最大的子串。根据题目描述，这个子串可以通过 lastSubstring 函数找到。
   • • lastSubstring 函数的作用是找到 word 的字典序最大的后缀（即从某个位置开始到末尾的子串）。
   • • 然后，我们需要考虑所有分割方式中可能产生的子串的最大值。由于分割方式不能重复，我们需要确保选取的子串尽可能长。
   • • 在 answerString 函数中，last 是 word 的字典序最大的后缀，然后根据 numFriends 的限制，截取 last 的前 min(m, n - numFriends + 1) 个字符。
5. 5. 示例分析：
   • • word = "dbca", numFriends = 2：
     • • lastSubstring("dbca") 的结果是 "dbca"（因为 "dbca" 是最大的后缀）。
     • • n = 4, m = 4, n - numFriends + 1 = 3。
     • • min(4, 3) = 3，所以结果是 "dbc"。

时间复杂度

1. 1. lastSubstring 函数：
   • • 使用双指针法，时间复杂度为 O(n)，其中 n 是 word 的长度。
   • • 最坏情况下，每个字符最多被比较两次（如 "aaaaa"），因此是线性时间。
2. 2. answerString 函数：
   • • 调用 lastSubstring 和简单的截取操作，时间复杂度为 O(n)。
3. 3. 总时间复杂度：O(n)。

空间复杂度

1. 1. lastSubstring 和 answerString 函数：
   • • 只使用了常数级别的额外空间（如指针和临时变量）。
2. 2. 总空间复杂度：O(1)。

总结

• • 通过双指针法高效找到字典序最大的后缀。
• • 根据 numFriends 的限制截取子串。
• • 时间复杂度和空间复杂度均为最优。

Go完整代码如下：

.

package main

import (
    "fmt"
)

func lastSubstring(s string)string {
    i, j, n := , , len(s)
    for j < n {
        k := 
        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+, i+k+)
        } else {
            j = j + k + 
        }
    }
    return s[i:]
}

func answerString(word string, numFriends int)string {
    if numFriends ==  {
        return word
    }
    last := lastSubstring(word)
    n, m := len(word), len(last)
    return last[:min(m, n-numFriends+)]
}

func main() {
    word := "dbca"
    numFriends := 
    result := answerString(word, numFriends)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def last_substring(s: str) -> str:
    i, j, n = , , len(s)
    while j < n:
        k = 
        while j + k < n and s[i + k] == s[j + k]:
            k += 
        if j + k < n and s[i + k] < s[j + k]:
            i, j = j, max(j + , i + k + )
        else:
            j = j + k + 
    return s[i:]


def answer_string(word: str, num_friends: int) -> str:
    if num_friends == :
        return word
    last = last_substring(word)
    n, m = len(word), len(last)
    return last[:min(m, n - num_friends + )]


if __name__ == "__main__":
    word = "dbca"
    num_friends = 
    result = answer_string(word, num_friends)
    print(result)

我们相信Go语言和算法为普通开发者提供了困境的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。