Split Message Based on Limit - Solution & Explanation
Problem Statement
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 <= 104messageconsists only of lowercase English letters and' '.1 <= limit <= 104
Approach Overview
Problem Overview: You need to split a string into multiple parts such that each part length does not exceed a given limit. Every part must include a suffix of the form <i/total>, where i is the current part index and total is the total number of parts. The challenge is that the suffix itself consumes characters, so the valid message length per part depends on the number of digits in i and total.
Approach 1: Brute Force Enumeration (O(n^2) time, O(n) space)
The direct idea is to try every possible value for the total number of parts k. For each candidate k, compute how many characters are available for the message after accounting for the suffix length <i/k>. Then simulate building all parts and check whether the entire string fits. Because suffix sizes change as i grows (1-digit, 2-digit, etc.), you must recalculate available capacity for each part. This approach repeatedly scans the string and recomputes capacities, which can push the time complexity to O(n^2). It works conceptually but becomes inefficient for long messages.
Approach 2: Dynamic Programming (O(n^2) time, O(n) space)
A dynamic programming formulation treats the problem as deciding how many characters to assign to each valid part while respecting the suffix constraint. Define states based on the current index in the string and the number of parts formed so far. The transition determines whether the next segment plus suffix fits within limit. This method systematically explores valid splits and avoids some redundant recomputation compared to brute force. However, because suffix lengths depend on both i and total, the state space grows quickly, making the solution more theoretical than practical for large inputs.
Approach 3: Greedy + Binary Search (O(n log n) time, O(n) space)
The optimal strategy observes that the only unknown is the total number of parts k. Once k is fixed, the suffix format <i/k> is fully determined, so you can calculate the capacity of each part and check if the message fits. Use binary search over possible values of k. For a candidate k, iterate from i = 1 to k, compute the suffix length using digit counts, and accumulate how many message characters can fit across all parts. If the total capacity covers the message length, the split is feasible. Once the smallest valid k is found, build the result sequentially using a string slice for each part and append the correct suffix. This reduces unnecessary trials and keeps the algorithm efficient.
Recommended for interviews: Interviewers expect the greedy feasibility check combined with binary search. It shows that you recognize the monotonic property of valid part counts and can reason about suffix overhead. Brute force demonstrates understanding of the constraints, but the greedy + binary search solution shows stronger algorithmic thinking and handles large inputs efficiently.
Approach 1: Dynamic Programming
This approach utilizes the dynamic programming paradigm to solve the problem. We store solutions of sub-problems to avoid redundant calculations, which improves efficiency significantly. The main idea is to break down the problem into simpler sub-problems, solve each of them once, and store their solutions. This typically involves creating a table to hold results of sub-problems and using these results to build up solutions to larger problems.
In this C implementation, we define a DP array to store the results of sub-problems. For each element, we store the sum of previous elements, thus constructing a solution from these smaller results. This allows us to find the result in a single pass.
Complexity
Time Complexity: O(n) since we iterate through the array once.
Space Complexity: O(n) because of the additional space used for the dynamic programming array.
Approach 2: Greedy Approach
The greedy approach aims to make optimal choices at each step with the hope of finding the global optimum. This often involves sorting, selection of maximum or minimum, or other simple calculations that lead directly to the solution.
This C solution finds the maximum value in a given array by iterating through the entire array. This greedy technique ensures that we capture the maximum element in linear time.
Complexity
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1) as it uses a constant amount of space.
Approach 3: Enumerate the Number of Segments + Simulation
We denote the length of the string message as n, and the number of segments as k.
According to the problem, if k > n, it means that we can divide the string into more than n segments. Since the length of the string is only n, dividing it into more than n segments will inevitably lead to some segments with a length of 0, which can be deleted. Therefore, we only need to limit the range of k to [1,.. n].
We enumerate the number of segments k from small to large. Let the length of a segments in all segments be sa, the length of b segments in all segments be sb, and the length of all symbols (including angle brackets and slashes) in all segments be sc.
Then the value of sa is {\textstyle sum_{j=1}^{k}} len(s_j), which can be directly obtained through the prefix sum; the value of sb is len(str(k)) times k; and the value of sc is 3 times k.
Therefore, the number of characters that can be filled in all segments is limittimes k - (sa + sb + sc). If this value is greater than or equal to n, it means that the string can be divided into k segments, and we can directly construct the answer and return it.
The time complexity is O(ntimes log n), where n is the length of the string message. Ignoring the space consumption of the answer, the space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming | Time Complexity: O(n) since we iterate through the array once. |
| Greedy Approach | Time Complexity: O(n), where n is the number of elements in the array. |
| Enumerate the Number of Segments + Simulation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^2) | O(n) | Useful for understanding the suffix constraint and validating small inputs |
| Dynamic Programming | O(n^2) | O(n) | When exploring structured split states or teaching DP transitions |
| Greedy + Binary Search | O(n log n) | O(n) | Best general solution; efficiently finds minimal valid part count |
Video Solution
Biweekly Contest 91 | Split Message Based on Limit • codingMohan • 3,567 views views
Watch 5 more video solutions →Frequently Asked Questions
Is Split Message Based on Limit easy or hard?
Split Message Based on Limit Python/Java solution
How to solve Split Message Based on Limit in O(n)?
What is the best approach for Split Message Based on Limit?
Is Split Message Based on Limit asked at Google/Amazon/Meta?
What data structure is used in Split Message Based on Limit?
What is the time complexity of Split Message Based on Limit?
Ready to solve this problem?
Practice Split Message Based on Limit with our built-in code editor and test cases.
Practice on FleetCode