# Split Message Based on Limit
**Difficulty:** HARD
[External](https://leetcode.com/problems/split-message-based-on-limit)
Canonical: https://scaleengineer.com/dsa/problems/split-message-based-on-limit
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** String
**Companies:** [Roblox](https://scaleengineer.com/companies/roblox), [Visa](https://scaleengineer.com/companies/visa), [Capital One](https://scaleengineer.com/companies/capital-one), [Databricks](https://scaleengineer.com/companies/databricks), [ZipRecruiter](https://scaleengineer.com/companies/ziprecruiter)
---
## Problem
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 <= 104`
* `message` consists only of lowercase English letters and `' '`.
* `1 <= limit <= 104`

# Approaches
## Linear Scan for Number of Parts
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public String[] splitMessage(String message, int limit) {
        int n = message.length();
        int b = 0; // optimal number of parts
        int totalSuffixLen = 0;

        for (int curB = 1; curB <= n; curB++) {
            int lenCurB = String.valueOf(curB).length();
            int lenLastPartNum = String.valueOf(curB).length();
            
            // Check if the limit is sufficient for the suffix of the last part
            if (limit <= 3 + lenCurB + lenLastPartNum) {
                continue;
            }

            // Calculate total length of suffixes for 'curB' parts
            int len1to9 = 1 * 9;
            int len10to99 = 2 * 90;
            int len100to999 = 3 * 900;
            int len1000to9999 = 4 * 9000;

            int currentTotalSuffixLen = 0;
            if (curB <= 9) {
                currentTotalSuffixLen = curB * (3 + lenCurB) + curB;
            } else if (curB <= 99) {
                currentTotalSuffixLen = curB * (3 + lenCurB) + len1to9 + (curB - 9) * 2;
            } else if (curB <= 999) {
                currentTotalSuffixLen = curB * (3 + lenCurB) + len1to9 + len10to99 + (curB - 99) * 3;
            } else {
                currentTotalSuffixLen = curB * (3 + lenCurB) + len1to9 + len10to99 + len100to999 + (curB - 999) * 4;
            }

            int remainingChars = n + currentTotalSuffixLen;
            if (remainingChars <= curB * limit) {
                b = curB;
                break;
            }
        }

        if (b == 0) {
            return new String[0];
        }

        String[] result = new String[b];
        int msgIdx = 0;
        for (int i = 1; i <= b; i++) {
            String suffix = "<" + i + "/" + b + ">";
            int payloadLen = limit - suffix.length();
            int end = Math.min(msgIdx + payloadLen, n);
            String msgPart = message.substring(msgIdx, end);
            result[i - 1] = msgPart + suffix;
            msgIdx = end;
        }

        return result;
    }
}
```
### 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.

## Binary Search over Monotonic Segments
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.
**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)`.
**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.
### Explanation
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`:
1.  We define a search range, e.g., for `d=2`, the range for `b` is `[10, 99]`.
2.  We first perform a basic check: if `limit <= 3 + 2*d`, no `b` in this segment can be valid, so we skip it.
3.  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`.
4.  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`.
5.  We run this binary search for each possible number of digits `d` and collect the smallest valid `b` found in each segment.
6.  The final answer is the minimum among all candidates found across all segments.
7.  If no valid `b` is found in any segment, it's impossible. Otherwise, we construct the result using the optimal `b`.

```java
class Solution {
    public String[] splitMessage(String message, int limit) {
        int n = message.length();
        int optimalB = -1;

        // Iterate through possible number of digits of b
        for (int d = 1; d < 10; d++) {
            long low = (long) Math.pow(10, d - 1);
            long high = (long) Math.pow(10, d) - 1;

            // The number of parts cannot exceed the message length in a practical sense
            if (low > n) break;
            high = Math.min(high, n);

            // Check if limit is sufficient for this number of digits
            if (limit <= 3 + d + d) {
                continue;
            }

            // Binary search for the smallest b in the range [low, high]
            long currentBestB = -1;
            while (low <= high) {
                long mid = low + (high - low) / 2;
                if (canSplit(n, limit, (int) mid)) {
                    currentBestB = mid;
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }

            if (currentBestB != -1) {
                if (optimalB == -1 || currentBestB < optimalB) {
                    optimalB = (int) currentBestB;
                }
            }
        }

        if (optimalB == -1) {
            return new String[0];
        }

        String[] result = new String[optimalB];
        int msgIdx = 0;
        for (int i = 1; i <= optimalB; i++) {
            String suffix = "<" + i + "/" + optimalB + ">";
            int payloadLen = limit - suffix.length();
            int end = Math.min(msgIdx + payloadLen, n);
            String msgPart = message.substring(msgIdx, end);
            result[i - 1] = msgPart + suffix;
            msgIdx = end;
        }
        return result;
    }

    private boolean canSplit(int n, int limit, int b) {
        long totalPayload = 0;
        int lenB = String.valueOf(b).length();
        
        // Efficiently calculate sum of lengths of numbers from 1 to b
        long sumOfLens = 0;
        long count = 9;
        for (int d = 1; d < lenB; d++) {
            sumOfLens += d * count;
            count *= 10;
        }
        sumOfLens += lenB * (b - Math.pow(10, lenB - 1) + 1);

        long totalSuffixOverhead = (long)b * (3 + lenB) + sumOfLens;
        long totalCapacity = (long)b * limit - totalSuffixOverhead;

        return totalCapacity >= n;
    }
}
```
### 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.

# Solutions
### Java

```java
class 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 ; } }
```

### Python

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

### CPP

```cpp
class 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 ; } };
```