#2468

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Split Message Based on Limit

Split Message Based on Limit requires dividing a string into parts with length constraints using a calculated suffix pattern.

string binary search enumeration

Problem Statement

You are given a string message and a positive integer limit. Your task is to split message into multiple parts such that each part includes a suffix in the format "<part_index>/<total_parts> ", and the total length of each part does not exceed limit. The last part can be shorter than limit. Parts must be split so that removing the suffix from all parts and concatenating them recreates message.

The goal is to produce the fewest number of parts possible while maintaining the suffix structure and respecting the length limit. Each part's content length is reduced by the length of its suffix, so planning the split requires calculating how many parts will exist and how many digits are needed for the suffix. You must return all parts in order with suffixes.

Examples

Example 1

Input: message = "this is really a very awesome message", limit = 9

Output: ["thi ","s i ","s r ","eal ","ly ","a v ","ery "," aw ","eso ","me "," m ","es ","sa ","ge "]

The first 9 parts take 3 characters each from the beginning of message. The next 5 parts take 2 characters each to finish splitting message. In this example, each part, including the last, has length 9. It can be shown it is not possible to split message into less than 14 parts.

Example 2

Input: message = "short message", limit = 15

Output: ["short mess ","age "]

Under the given constraints, the string can be split into two parts:

The first part comprises of the first 10 characters, and has a length 15.
The next part comprises of the last 3 characters, and has a length 8.

Constraints

1 <= message.length <= 104
message consists only of lowercase English letters and ' '.
1 <= limit <= 104

Solution Approach

Calculate Suffix Length Dynamically

First, compute how many parts the message will need. The suffix length depends on the total number of parts and the current part index, so we must handle variable-length numbers. Use enumeration to simulate splits and verify if each candidate number of parts fits the limit when including the suffix.

Binary Search Over Part Counts

Apply binary search on the possible number of parts. For each midpoint, check if the message can be split into that many parts under the limit including suffixes. This approach efficiently finds the minimal valid number of parts, aligning with the problem's binary search over answer space pattern.

Construct Final Parts

Once the minimal part count is determined, build each part by taking as many characters as allowed given its suffix. Append the suffix to each part, and ensure the last part may be shorter than the limit. Return the array of parts preserving original message order.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Enumerate the Number of Segments + Simulation

We denote the length of the string `message` as $n$, and the number of segments as $k$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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 []

Continue Practicing

#2437 number of valid clock times #2565 subsequence with the minimum score #2309 greatest english letter in upper and lower case