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 <= 104Problem 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.
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.
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.
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.
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 | 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. |
| 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 |
Biweekly Contest 91 | Split Message Based on Limit • codingMohan • 3,497 views views
Watch 5 more video solutions →Practice Split Message Based on Limit with our built-in code editor and test cases.
Practice on FleetCode