How do I handle suffix length for Split Message Based on Limit?

Calculate the number of digits in total parts and each index to determine suffix length, then adjust content length accordingly.

Can all parts except the last be exactly the limit length?

Yes, but only after accounting for the suffix. The last part may be shorter if remaining characters are less than limit minus suffix.

Why use binary search in this problem?

Binary search efficiently finds the minimal number of parts that satisfy the limit with suffixes, avoiding brute-force enumeration over all splits.

What if the message length is smaller than limit?

In this case, the message forms a single part with a suffix, which may be shorter than the limit, satisfying the constraints.

Is there a pattern to splitting the message?

Yes, the pattern involves taking as many characters as allowed for each part given the suffix, iterating from the first to the last part, ensuring minimal total parts.

#2468

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

根据限制分割消息

给你一个字符串 message 和一个正整数 limit 。你需要根据 limit 将 message 分割成一个或多个部分。每个部分的结尾都是 " " ，其中 "b" 用分割出来的总数替换， "a" 用当前部分所在的编号替换，编号从 1 到 b 依次编号。除此以外，除了最后一部分长…

字符串二分查找枚举

题目描述

给你一个字符串 message 和一个正整数 limit 。

你需要根据 limit 将 message 分割成一个或多个部分。每个部分的结尾都是 "<a/b>" ，其中 "b" 用分割出来的总数替换， "a" 用当前部分所在的编号替换，编号从 1 到 b 依次编号。除此以外，除了最后一部分长度 小于等于 limit 以外，其他每一部分（包括结尾部分）的长度都应该等于 limit 。

你需要确保分割后的结果数组，删掉每部分的结尾并 按顺序 连起来后，能够得到 message 。同时，结果数组越短越好。

请你返回 message 分割后得到的结果数组。如果无法按要求分割 message ，返回一个空数组。

示例 1：

输入：message = "this is really a very awesome message", limit = 9
输出：["thi<1/14>","s i<2/14>","s r<3/14>","eal<4/14>","ly <5/14>","a v<6/14>","ery<7/14>"," aw<8/14>","eso<9/14>","me<10/14>"," m<11/14>","es<12/14>","sa<13/14>","ge<14/14>"]
解释：
前面 9 个部分分别从 message 中得到 3 个字符。
接下来的 5 个部分分别从 message 中得到 2 个字符。
这个例子中，包含最后一个部分在内，每个部分的长度都为 9 。
可以证明没有办法分割成少于 14 个部分。

示例 2：

输入：message = "short message", limit = 15
输出：["short mess<1/2>","age<2/2>"]
解释：
在给定限制下，字符串可以分成两个部分：
- 第一个部分包含 10 个字符，长度为 15 。
- 第二个部分包含 3 个字符，长度为 8 。

提示：

1 <= message.length <= 10⁴
message 只包含小写英文字母和 ' ' 。
1 <= limit <= 10⁴

lightbulb

解题思路

方法一：枚举分段数量 + 模拟

我们设字符串 message 的长度为 $n$ ，分段数量为 $k$ 。

根据题意，如果 $k \gt n$ ，表示我们可以将字符串划分成超过 $n$ 段，由于字符串长度仅为 $n$ ，若划分成超过 $n$ 段必然导致有部分段的长度为 $0$ ，可以删去。因此，我们只需要将 $k$ 的取值范围限制在 $[1,.. n]$ 即可。

从小到大枚举分段数量 $k$ ，记所有分段中 $a$ 段的长度为 $sa$ ，所有分段中 $b$ 段的长度为 $sb$ ，所有分段中符号（包括尖括号和斜杠）的长度为 $sc$ 。

那么 $sa$ 的值为 ${\textstyle \sum_{j=1}^{k}} len(s_j)$ ，可以直接通过前缀和求出；而 $sb$ 的值为 $len(str(k)) \times k$ ；另外 $sc$ 的值为 $3 \times k$ 。

因此，所有分段剩余可填充的字符数为 $limit\times k - (sa + sb + sc)$ ，如果该值大于等于 $n$ 则说明可以将字符串划分成 $k$ 段，直接构造答案返回即可。

时间复杂度 $O(n\times \log n)$ ，其中 $n$ 为字符串 message 的长度。忽略答案的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def splitMessage(self, message: str, limit: int) -> List[str]:
        n = len(message)
        sa = 0
        for k in range(1, n + 1):
            sa += len(str(k))
            sb = len(str(k)) * k
            sc = 3 * k
            if limit * k - (sa + sb + sc) >= n:
                ans = []
                i = 0
                for j in range(1, k + 1):
                    tail = f'<{j}/{k}>'
                    t = message[i : i + limit - len(tail)] + tail
                    ans.append(t)
                    i += limit - len(tail)
                return ans
        return []

speed

复杂度分析

指标	值
时间	complexity depends on the number of candidate splits checked by binary search and the cost to verify each split, typically O(n log n). Space complexity is O(n) for storing the resulting parts.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ask how to handle the variable suffix length when splitting message.
question_mark
Check if the candidate solution respects the limit including the suffix.
question_mark
Prompt for optimizing the number of parts instead of greedily splitting.

warning

常见陷阱

外企场景

error
Ignoring that the suffix length changes with the number of digits in total parts.
error
Assuming all parts except the last have exactly limit characters without adjusting for suffix.
error
Splitting greedily without verifying the minimal number of parts can cause failure.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow messages with punctuation or uppercase letters, requiring the same split logic.
arrow_right_alt
Change suffix format to include custom delimiters while keeping binary search strategy.
arrow_right_alt
Enforce an exact length for the last part, testing edge handling in binary search validation.

help

常见问题

外企场景

继续练习

#2437 有效时间的数目 #2565 最少得分子序列 #2309 兼具大小写的最好英文字母