You are given a string, message, and a positive integer, limit.
You must split message into one or more parts based on limit. Each resulting part should have the suffix "<a/b>", where "b" is to be replaced with the total number of parts and "a" is to be replaced with the index of the part, starting from 1 and going up to b. Additionally, the length of each resulting part (including its suffix) should be equal to limit, except for the last part whose length can be at most limit.
The resulting parts should be formed such that when their suffixes are removed and they are all concatenated in order, they should be equal to message. Also, the result should contain as few parts as possible.
Return the parts message would be split into as an array of strings. If it is impossible to split message as required, return an empty array.
Example 1:
Input: message = "this is really a very awesome message", limit = 9 Output: ["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>"] Explanation: 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<1/2>","age<2/2>"] Explanation: 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 <= 104message consists only of lowercase English letters and ' '.1 <= limit <= 104In #2468 Split Message Based on Limit, the challenge is to divide a message into multiple parts such that each part (including its suffix like <i/total>) does not exceed a given character limit. The tricky part is that the suffix length changes depending on the total number of parts, which affects how much of the original message can fit in each segment.
A common strategy is to search for the correct number of parts. For a guessed total number of segments, calculate how many characters are consumed by the suffix in each part and determine how many message characters remain. If the entire message can fit within these constraints, the split is valid.
Since the number of segments influences the suffix size, some implementations use binary search or iterative checks to efficiently find a feasible count. Once the correct number of parts is identified, construct each segment accordingly. The approach focuses on careful string length accounting and efficient feasibility checks.
The overall complexity is typically O(n log n) or O(n) depending on the search strategy, with linear space used for storing the resulting message segments.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Binary Search on Number of Parts | O(n log n) | O(n) |
| Iterative Feasibility Check | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Could you solve the problem if you knew how many digits the total number of parts has?
Try all possible lengths of the total number of parts, and see if the string can be split such that the total number of parts has that length.
Binary search can be used for each part length to find the precise number of parts needed.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems involving string manipulation, constraints, and feasibility checks like this one are common in technical interviews. They test attention to detail, edge-case handling, and the ability to design efficient validation logic.
A common optimal strategy is to determine the number of parts the message must be split into and verify whether each segment can fit within the limit when the suffix <i/total> is included. Many solutions iterate or use binary search to test feasible segment counts before constructing the final parts.
Each split message must include a suffix indicating its index and the total number of parts. As the total number of segments grows, the suffix length also increases, reducing the space available for actual message characters in each part.
The problem mainly relies on string manipulation and arrays or lists to store the resulting segments. The key challenge is not the data structure but correctly calculating lengths and handling suffix formatting efficiently.