Split Message Based on Limit

Hard

#2252Time: O(N * log N), where N is the length of the message. The main loop runs up to N times. Inside the loop, calculating the total suffix length involves operations that are proportional to the number of digits in `b`, which is `O(log b)` or `O(log N)`. The final step of constructing the result array takes `O(b * log b)`, which in the worst case is `O(N * log N)`.Space: O(N) to store the resulting array of strings. The length of the concatenated parts is equal to the original message length plus the length of all suffixes.5 companies

Patterns

Enumeration

Algorithms

Binary Search

Data structures

String

Companies

Roblox Visa Capital One Databricks

Prompt

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 <= 10⁴
message consists only of lowercase English letters and ' '.
1 <= limit <= 10⁴

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through all possible numbers of parts, b, starting from 1. For each b, it calculates the total message capacity it can hold. The first b that provides enough capacity is the one with the minimum number of parts. A key insight is that the capacity function is not monotonic over the entire range of b (it dips when b crosses a power of 10), so a simple binary search over all possible b values is not feasible, making a linear scan a straightforward way to find the solution.

Algorithm

Iterate through the number of parts b from 1 up to message.length.
For each b, determine len_b, the number of digits in b.
Check if the limit is large enough for any suffix: limit > 3 + 2 * len_b. If not, this b (and any other with the same len_b) is invalid.
Calculate the total capacity for b parts. This is the total characters available for the message content across all parts.
The total capacity can be calculated as b * limit - total_suffix_lengths.
If total_capacity >= message.length, we have found the minimum b.
Store this b and break the loop.
If no such b is found after checking all possibilities, return an empty array.
Otherwise, construct the result array of b parts. For each part i, calculate the suffix <i/b>, determine the message chunk size, and create the final part string.

Walkthrough

The core of this method is to find the smallest integer b (number of parts) for which the given message can be split according to the rules.

For a given number of parts b, each part i (from 1 to b) will have a suffix of the form <i/b>. The length of this suffix is 3 + length(i) + length(b). The maximum number of characters from the message that part i can hold (its payload) is limit - (3 + length(i) + length(b)).

The total capacity for b parts is the sum of the payloads of all b parts. Let's call this capacity(b). We are looking for the smallest b such that capacity(b) >= message.length.

The formula for total capacity is: capacity(b) = Σ (limit - (3 + length(i) + length(b))) for i from 1 to b. This simplifies to: capacity(b) = b * (limit - 3 - length(b)) - Σ length(i) for i from 1 to b.

The algorithm iterates b from 1 upwards. In each iteration, it calculates capacity(b) and checks if it's sufficient. A crucial prerequisite is that the limit must be large enough to accommodate the longest possible suffix for b parts, which occurs for part b itself. The condition is limit > 3 + 2 * length(b). If this condition fails, b parts are not possible.

Once the smallest b is found, the message is split. For each part i from 1 to b-1, we take a chunk of the message of size equal to its full payload. The last part takes the rest of the message.

1class Solution {2    public String[] splitMessage(String message, int limit) {3        int n = message.length();4        int b = 0; // optimal number of parts5        int totalSuffixLen = 0;6 7        for (int curB = 1; curB <= n; curB++) {8            int lenCurB = String.valueOf(curB).length();9            int lenLastPartNum = String.valueOf(curB).length();10            11            // Check if the limit is sufficient for the suffix of the last part12            if (limit <= 3 + lenCurB + lenLastPartNum) {13                continue;14            }15 16            // Calculate total length of suffixes for 'curB' parts17            int len1to9 = 1 * 9;18            int len10to99 = 2 * 90;19            int len100to999 = 3 * 900;20            int len1000to9999 = 4 * 9000;21 22            int currentTotalSuffixLen = 0;23            if (curB <= 9) {24                currentTotalSuffixLen = curB * (3 + lenCurB) + curB;25            } else if (curB <= 99) {26                currentTotalSuffixLen = curB * (3 + lenCurB) + len1to9 + (curB - 9) * 2;27            } else if (curB <= 999) {28                currentTotalSuffixLen = curB * (3 + lenCurB) + len1to9 + len10to99 + (curB - 99) * 3;29            } else {30                currentTotalSuffixLen = curB * (3 + lenCurB) + len1to9 + len10to99 + len100to999 + (curB - 999) * 4;31            }32 33            int remainingChars = n + currentTotalSuffixLen;34            if (remainingChars <= curB * limit) {35                b = curB;36                break;37            }38        }39 40        if (b == 0) {41            return new String[0];42        }43 44        String[] result = new String[b];45        int msgIdx = 0;46        for (int i = 1; i <= b; i++) {47            String suffix = "<" + i + "/" + b + ">";48            int payloadLen = limit - suffix.length();49            int end = Math.min(msgIdx + payloadLen, n);50            String msgPart = message.substring(msgIdx, end);51            result[i - 1] = msgPart + suffix;52            msgIdx = end;53        }54 55        return result;56    }57}

Complexity

Time

O(N * log N), where N is the length of the message. The main loop runs up to N times. Inside the loop, calculating the total suffix length involves operations that are proportional to the number of digits in `b`, which is `O(log b)` or `O(log N)`. The final step of constructing the result array takes `O(b * log b)`, which in the worst case is `O(N * log N)`.

Space

O(N) to store the resulting array of strings. The length of the concatenated parts is equal to the original message length plus the length of all suffixes.

Trade-offs

Pros

Relatively simple to understand and implement compared to more optimized solutions.
Correctly handles the non-monotonic nature of the capacity function, which is a tricky aspect of the problem.

Cons

The time complexity of O(N * log N) can be slow if message.length is very large, although it might pass within typical time limits.
It performs many redundant calculations as it iterates, especially for the sum of lengths of i part.

This approach optimizes the search for the minimum number of parts b. It observes that while the total capacity function C(b) is not globally monotonic, it is monotonic within specific segments where the number of digits in b remains constant (e.g., [1, 9], [10, 99], etc.). By performing a binary search for a valid b within each of these few segments, we can find the optimal b much faster than a linear scan.

Algorithm

Initialize optimal_b = -1.
Iterate through the number of digits d that b can have (e.g., 1 to 5).
For each d, define a search range for b, e.g., [10, 99] for d=2.
If limit is too small for suffixes with d digits (limit <= 3 + 2*d), skip this segment.
Perform binary search for b within this monotonic segment.
The check inside the binary search, canSplit(b), calculates capacity(b) and returns true if capacity(b) >= message.length.
If the binary search finds a valid b for the segment, update optimal_b with the minimum value found so far.
After checking all segments, if optimal_b is still -1, no solution exists.
Otherwise, optimal_b holds the minimum number of parts. Construct and return the result array.

Walkthrough

The number of parts b can have 1, 2, 3, 4, or 5 digits (since message.length <= 10^4). This creates a small, constant number of segments to analyze.

For each segment, defined by the number of digits d in b:

We define a search range, e.g., for d=2, the range for b is [10, 99].
We first perform a basic check: if limit <= 3 + 2*d, no b in this segment can be valid, so we skip it.
Within a segment, length(b) is constant (d). The capacity function C(b) = b * (limit - 3 - d) - Σ length(i) becomes monotonic with respect to b.
This monotonicity allows us to use binary search within the range [10^(d-1), 10^d - 1] to find the smallest b in that segment that satisfies C(b) >= message.length.
We run this binary search for each possible number of digits d and collect the smallest valid b found in each segment.
The final answer is the minimum among all candidates found across all segments.
If no valid b is found in any segment, it's impossible. Otherwise, we construct the result using the optimal b.

1class Solution {2    public String[] splitMessage(String message, int limit) {3        int n = message.length();4        int optimalB = -1;5 6        // Iterate through possible number of digits of b7        for (int d = 1; d < 10; d++) {8            long low = (long) Math.pow(10, d - 1);9            long high = (long) Math.pow(10, d) - 1;10 11            // The number of parts cannot exceed the message length in a practical sense12            if (low > n) break;13            high = Math.min(high, n);14 15            // Check if limit is sufficient for this number of digits16            if (limit <= 3 + d + d) {17                continue;18            }19 20            // Binary search for the smallest b in the range [low, high]21            long currentBestB = -1;22            while (low <= high) {23                long mid = low + (high - low) / 2;24                if (canSplit(n, limit, (int) mid)) {25                    currentBestB = mid;26                    high = mid - 1;27                } else {28                    low = mid + 1;29                }30            }31 32            if (currentBestB != -1) {33                if (optimalB == -1 || currentBestB < optimalB) {34                    optimalB = (int) currentBestB;35                }36            }37        }38 39        if (optimalB == -1) {40            return new String[0];41        }42 43        String[] result = new String[optimalB];44        int msgIdx = 0;45        for (int i = 1; i <= optimalB; i++) {46            String suffix = "<" + i + "/" + optimalB + ">";47            int payloadLen = limit - suffix.length();48            int end = Math.min(msgIdx + payloadLen, n);49            String msgPart = message.substring(msgIdx, end);50            result[i - 1] = msgPart + suffix;51            msgIdx = end;52        }53        return result;54    }55 56    private boolean canSplit(int n, int limit, int b) {57        long totalPayload = 0;58        int lenB = String.valueOf(b).length();59        60        // Efficiently calculate sum of lengths of numbers from 1 to b61        long sumOfLens = 0;62        long count = 9;63        for (int d = 1; d < lenB; d++) {64            sumOfLens += d * count;65            count *= 10;66        }67        sumOfLens += lenB * (b - Math.pow(10, lenB - 1) + 1);68 69        long totalSuffixOverhead = (long)b * (3 + lenB) + sumOfLens;70        long totalCapacity = (long)b * limit - totalSuffixOverhead;71 72        return totalCapacity >= n;73    }74}

Complexity

Time

O(D * log(R) * log(R) + N * log N). `D` is the number of digit segments (a small constant, ~5). `R` is the size of the largest segment (~N). The search for `b` is very fast, `O((log N)^2)`. The dominant factor is the final construction of the result array, which takes `O(b * log b)`. In the worst case, `b` can be on the order of `N`, making this step `O(N * log N)`.

Space

O(N) for storing the result array. The space required for variables during the search is negligible, `O(log N)`.

Trade-offs

Pros

Significantly faster at finding the optimal b than a linear scan, with a time complexity of roughly O((log N)^2) for the search part.
An elegant solution that correctly handles the problem's non-monotonic property by breaking it down into monotonic subproblems.

Cons

More complex to implement due to the nested logic of iterating through segments and performing a binary search within each.
The overall time complexity is still dominated by the final string construction step in the worst case.

Solutions

Solution

1class Solution { public String [] splitMessage ( String message , int limit ) { int n = message . length (); int sa = 0 ; String [] ans = new String [ 0 ]; for ( int k = 1 ; k <= n ; ++ k ) { int lk = ( k + "" ). length (); sa += lk ; int sb = lk * k ; int sc = 3 * k ; if ( limit * k - ( sa + sb + sc ) >= n ) { int i = 0 ; ans = new String [ k ]; for ( int j = 1 ; j <= k ; ++ j ) { String tail = String . format ( "<%d/%d>" , j , k ); String t = message . substring ( i , Math . min ( n , i + limit - tail . length ())) + tail ; ans [ j - 1 ] = t ; i += limit - tail . length (); } break ; } } return ans ; } }

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

1class Solution { public: vector < string > splitMessage ( string message , int limit ) { int n = message . size (); int sa = 0 ; vector < string > ans ; for ( int k = 1 ; k <= n ; ++ k ) { int lk = to_string ( k ). size (); sa += lk ; int sb = lk * k ; int sc = 3 * k ; if ( k * limit - ( sa + sb + sc ) >= n ) { int i = 0 ; for ( int j = 1 ; j <= k ; ++ j ) { string tail = "<" + to_string ( j ) + "/" + to_string ( k ) + ">" ; string t = message . substr ( i , limit - tail . size ()) + tail ; ans . emplace_back ( t ); i += limit - tail . size (); } break ; } } return ans ; } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem