LeetCode每日一题2025-06-04

点击获取AI摘要

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

给你一个字符串 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 * 10³
• word 仅由小写英文字母组成。
• 1 <= numFriends <= word.length

问题分析

给定一个长度为 $n$ 的字符串 word 和一个整数 numFriends = k，每一轮都会将 word 分成 $k$ 个非空子串，并将这 $k$ 个子串放入一个盒子里。不同轮次的分割方式不能完全相同。我们需要在所有可能的轮次结束后，找到盒子中所有子串里字典序最大的那个子串，并返回它。

• 记 $n = \text{word.length}$。每一次分割会在原字符串上选出 $k - 1$ 个分隔点，将整个字符串切成 $k$ 段。每一段都是非空的。

• 考虑任意一个子串 $\text{word}[l:r]$（右开区间），它出现在某一次分割中的条件是什么？

  1. 这段子串占据了原始字符串从 [l, r) 这部分，中间不一定有分隔点。
  2. 它左边还剩下 $l$ 个字符，需要被 $a$ 个分割点切成 $a$ 段；它右边还剩 $n - r$ 个字符，需要被 $b$ 个分割点切成 $b$ 段。
  3. 因为总共要切 $k-1$ 个分隔点，所以 $a + b = k - 1$。而要能把左边 $l$ 个字符分成 $a$ 段，需要$a \le l$；要能把右边 $n - r$ 个字符分成 $b$ 段，需要 $b \le n - r$。

  因此，只要满足

  $$\exists\,a, b \ge 0,\quad a + b = k - 1,\quad a \le l,\quad b \le n-r,$$

  就说明子串 $\text{word}[l:r]$ 可以作为某一次切分中间的某一段。注意因为 $a+b=k-1$，只要 $l + (n - r) \ge k - 1$ 就一定可以找到满足条件的 $a,b$。
  化简之后，该条件等价于

  $$l + (\,n - r\,) \;\ge\; k - 1 \quad\Longleftrightarrow\quad r \;\le\; n + l - (k - 1).$$

• 对于固定的起点 $l$，能出现的最长子串（右端点最大）就是

  $$r_{\max}(l) \;=\; \min\bigl(n,\;n + l - (k-1)\bigr).$$

  同时因为子串必须非空，所以要求 $r > l$，或者等价 $r_{\max}(l) \ge l + 1$。可以验证 $k \le n$ 时，所有 $0 \le l \le n-1$ 都满足 $n + l - (k-1) \ge l + 1$，因此每个 $l$ 都有至少一个合法子串。

• 于是，所有可能进入盒子的子串都满足：

  $$\text{word}[\,l : r\,]\,,\quad 0 \le l < r \le r_{\max}(l)\,.$$

  要找的答案，就是这所有子串集合当中字典序最大的那一个。

算法思路

算法类别（Tags）

• 字符串处理（需要在海量子串里比较字典序）
• 滚动哈希 + 二分查找（用于高效比较任意两段子串的 LCP 并判断字典序）
• 枚举 + 贪心（我们枚举所有可能的起点 $l$，然后只保留“该起点下的最优”并和当前全局最优做比较）

核心思路概述

• 由于 $n \le 5000$，暴力枚举所有子串 $O(n^2)$ 然后直接比较会超时。

• 观察到，对于固定起点 $l$，所有合法子串 $[l : r]$ 中，字典序最大的一定是“尽可能延伸到右”的那个 $\text{word}[l : r_{\max}(l)]$。理由：如果在两个都从 $l$ 出发的子串 $\text{word}[l : r_1]$ 和 $\text{word}[l : r_2]$ 之间比较，且 $r_2 > r_1$，那么这两个子串在前 $\min(r_1 - l, r_2 - l) = r_1 - l$ 个字符上相同；如果它们在这一段都相同，那么更长的那一个一定在“被短串全部匹配”后还能继续比（短串结束后，长串更大），所以更长的必然字典序更大。

• 因此我们只需要枚举 $l = 0, 1, \dots, n-1$，针对每个 $l$ 只生成一个候选子串：

  $$S_l = \text{word}\bigl[l : r_{\max}(l)\bigr],\qquad r_{\max}(l) = \min\bigl(n,\;n+l-(k-1)\bigr).$$

• 最后只需要在这 $ n $ 个长度不一的子串 ${S_0, S_1,\dots,S_{n-1}}$ 里找一个字典序最大的。

如何在 $ n $ 个长度各异的子串中高效比较字典序？

• 如果我们直接用 Python 的 str 比较 (>) 来暴力比较长达 $ O(n) $ 的字符，对比 $ O(n) $ 次，最坏会 $O(n^2)$ 的字符访问，当 $n=5000$ 时约为 $2.5\times10^7$ 次字符比较，比较吃力，且每次比较会断言到底多长才能判定大小。

• 更优的做法是：预处理滚动哈希 (rolling hash)，再用 “二分查找+哈希” 方法快速算出任意两段子串的最长公共前缀 (LCP)，从而在 $O(\log n)$ 时间内完成一次“两个子串谁字典序大”的判断。

• 具体做法：

  1. 先把 word 的每个字符数值化（如 ord(char)-'a'+1），滚动哈希采用一个大素数模数，比如 $10^9+7$，以及一个随机基数 BASE（常见取 131、91138233 等）。预计算：

     $$H[i] = \bigl(\text{hash of prefix }\text{word}[0:i]\bigr),\quad P[i] = \text{BASE}^i \bmod \text{MOD} \quad (i=0\ldots n).$$

     这样就能 $O(1)$ 时间算出任意子串 $\text{word}[l:r]$ 的哈希。

  2. 要比较 $S_{l_1} = \text{word}[l_1 : r_{\max}(l_1)]$ 和 $S_{l_2} = \text{word}[l_2 : r_{\max}(l_2)]$ 这两段子串的字典序时：

     • 先算出它们长度 $\ell_1 $ 和 $ \ell_2$。令 $\ell = \min(\ell_1,\ell_2)$。
     • 用二分窗口在 $[0,\ell]$ 范围内找出最长公共前缀长度 LCP。即二分 mid，比较 $\text{hash}(l_1, l_1+\text{mid})$ 和 $\text{hash}(l_2, l_2+\text{mid})$。若相等，说明前 mid 相同，往右扩；否则往左缩。
     • 得到 LCP = d。
       1. 如果 $d = \ell$，说明短的那个子串前 $\ell$ 都被长子串匹配完了，于是短串更短，根据“较短前缀相同时，短串字典序更小”的原则，此时 $\ell_1 = \ell_2$ 两串相等；若 $\ell_1 < \ell_2$ 则 $S_{l_1} < S_{l_2}$，反之亦然。
       2. 否则 $d < \ell$，此时二分定位到第一个不相同的位置：比较 word[l1 + d] 与 word[l2 + d] 即可判定哪个更大。

• 这样，对于任意两段子串，只需要 $O(\log n)$ 步二分，每步 $O(1)$ 哈希比较，就能决定它们谁更大。我们对所有 $l = 0,\dots,n-1$ 的 $S_l$ 做一次“与目前最优做比较”，总共做 $n$ 次比较，整体复杂度为 $O(n \log n)$。

时间复杂度

预处理哈希：$O(n)$

枚举 $n$ 个起点，每次做一次“二分查找 + 哈希比较”找到 LCP：$O(\log n)$

总计：$O\bigl(n \log n\bigr)$

空间：$O(n)$ 存储哈希、幂次表、以及索引等。

代码分解

预处理阶段（滚动哈希预计算）

• 计算 P[i] = BASE^i mod MOD，和 H[i] = hash(word[0:i])，一共 $O(n)$ 时间。

枚举每个起点 $l$ 并生成候选子串 $S_l$

• 对于 $l = 0..n-1$，先算出

$$r_{\max}(l) = \min\bigl(n,\;n + l - (k-1)\bigr),\quad \ell_l = r_{\max}(l) - l\;(\text{即子串长度}).$$

只要 $\ell_l \ge 1$（总会满足，因为 $k \le n$），就把它当作一个候选。

• 设 best_l = 0（初始假定第一个子串最优），然后依次枚举 l = 1..n-1：

  1. 调用函数 isLeftGreater(l, best_l) 判断 $S_l$ 与 $S_{\text{best\_l}}$ 哪个字典序更大。
  2. 如果 $S_l > S_{\text{best\_l}}$，就 best_l = l。

比较子串的实现细节

• 先算出两段子串的长度 $\ell_1$ 和 $\ell_2$，令 $\ell = \min(\ell_1, \ell_2)$；
• 二分查找 $d$ 满足：hash(l1, l1+d) == hash(l2, l2+d)，同时 hash(l1, l1+d+1) != hash(l2, l2+d+1)（若存在差异），这样就得到它们的最长公共前缀 $d$。
• 若 $d == \ell$，那么较短的前缀全部相同，短串字典序更小，长串更大；
• 否则，直接比较 word[l1 + d] 和 word[l2 + d]。

代码实现

class Solution:
    def answerString(self, word: str, numFriends: int) -> str:
        """
        返回所有合法切分产生的子串中，字典序最大的那个子串。
        """
        s = word
        n = len(s)
        k = numFriends

        # 特殊情况：k = 1 时，只能分成一个子串，即整个字符串本身
        if k == 1:
            return s

        # 1. 哈希参数
        MOD = 10**9 + 7
        BASE = 91138233

        # 2. 预计算 powers[i] = BASE^i % MOD
        powers = [1] * (n + 1)
        for i in range(1, n + 1):
            powers[i] = (powers[i - 1] * BASE) % MOD

        # 3. 预计算前缀哈希 H[i] = hash(s[0:i])
        H = [0] * (n + 1)
        for i, ch in enumerate(s):
            cval = ord(ch) - ord('a') + 1
            H[i + 1] = (H[i] * BASE + cval) % MOD

        def get_hash(l: int, r: int) -> int:
            """
            返回子串 s[l:r] 的哈希值（0-based，右开区间）。
            hash(l,r) = (H[r] - H[l] * powers[r-l]) % MOD
            保证非负。
            """
            raw = H[r] - (H[l] * powers[r - l] % MOD)
            if raw < 0:
                raw += MOD
            return raw

        def lcp_length(l1: int, r1: int, l2: int, r2: int) -> int:
            """
            给定 s[l1:r1] 和 s[l2:r2]，返回它们的最长公共前缀长度 d。
            在 [0 .. min_len] 上二分，用哈希比较前 mid 个字符是否相同。
            """
            len1 = r1 - l1
            len2 = r2 - l2
            low, high = 0, min(len1, len2)
            while low < high:
                mid = (low + high + 1) // 2
                if get_hash(l1, l1 + mid) == get_hash(l2, l2 + mid):
                    low = mid
                else:
                    high = mid - 1
            return low

        def compare_segments(l1: int, r1: int, l2: int, r2: int) -> bool:
            """
            比较 s[l1:r1] 和 s[l2:r2] 的字典序：
            如果 s[l1:r1] > s[l2:r2] 返回 True，否则返回 False。
            """
            len1 = r1 - l1
            len2 = r2 - l2
            d = lcp_length(l1, r1, l2, r2)
            # 如果公共前缀长度等于较短那个子串长度，较长子串更大
            if d == min(len1, len2):
                return len1 > len2
            # 否则在第 d 个位置就能判断大小
            return s[l1 + d] > s[l2 + d]

        # 4. 枚举每个起点 l，计算合法的 r_max(l)，更新最优子串
        def r_max_for_l(l: int) -> int:
            """
            根据上述推导，当 k >= 2 时：
            r_max(l) =
              - n - (k-1),         if l == 0
              - n + l - (k-1),     if 1 <= l <= k-2
              - n,                 if l >= k-1
            """
            if l == 0:
                return n - (k - 1)
            if l <= k - 2:
                return n + l - (k - 1)
            return n

        # 初始化最优子串对应的区间 best_l, best_r
        best_l = 0
        best_r = r_max_for_l(0)

        # 枚举 l = 1 .. n-1
        for l in range(1, n):
            rmax = r_max_for_l(l)
            # 如果 rmax <= l，说明没有合法的非空子串，跳过
            if rmax <= l:
                continue
            # 比较 s[l:rmax] 与 当前最优 s[best_l:best_r]
            if compare_segments(l, rmax, best_l, best_r):
                best_l, best_r = l, rmax

        # 返回字典序最大的子串
        return s[best_l:best_r]