LeetCode Problem 2468

Difficulty: 🔴 Hard
Topics: String, Enumeration

Solution

LeetCode 2468 - Split Message Based on Limit

Problem Understanding

This problem asks us to divide a message into multiple parts while respecting a strict maximum length constraint for every part. Each part must include a suffix in the format "<a/b>", where:

• a is the current part number, starting from 1
• b is the total number of parts

The important detail is that the suffix itself consumes part of the allowed length. This means the actual amount of message content that can fit into each part depends on the size of the suffix.

For example, if limit = 15 and the suffix is "<1/10>", then the suffix length is 6, leaving only 9 characters available for message content in that part.

The split must satisfy several conditions simultaneously:

1. Every part except possibly the last must have length exactly equal to limit.
2. The last part may be shorter, but cannot exceed limit.
3. Removing all suffixes and concatenating the remaining text must reconstruct the original message exactly.
4. The number of parts must be minimized.
5. If no valid split exists, we return an empty array.

The constraints are large enough to prevent inefficient brute force solutions. The message length can be up to 10^4, which means we need a near linear or mildly quadratic approach.

A particularly tricky aspect of this problem is that the suffix length changes depending on the number of digits in both a and b. For example:

• "<1/9>" has length 5
• "<1/10>" has length 6
• "<10/100>" has length 9

Because of this, the capacity available for message characters is not fixed across all parts.

Another important edge case is when the suffix itself already exceeds the limit. For instance:

limit = 5
suffix = "<1/1>"
length = 5

This leaves zero room for actual message content, which makes splitting impossible unless the message is empty, which the constraints do not allow.

Approaches

Brute Force Approach

A brute force solution would try every possible number of parts b, then attempt to simulate the split for that value.

For each candidate b:

1. Compute the suffix length for every part.
2. Determine how many message characters each part can hold.
3. Check whether the total capacity across all parts is enough to store the entire message.
4. If valid, construct the answer.

This works because eventually one of the candidate values for b either succeeds or proves the task impossible.

However, the naive implementation can become expensive because for every candidate b, we may repeatedly recompute digit counts and capacities across all parts. If implemented carelessly, this can degrade toward quadratic behavior.

Optimal Insight

The key observation is that the total number of parts b completely determines all suffix formats.

Once b is fixed:

• Every suffix becomes known.
• The content capacity of every part becomes known.
• We can directly calculate whether the message fits.

The optimal strategy is therefore:

1. Enumerate possible values of b from 1 upward.
2. For each b, calculate the total usable message capacity.
3. The first feasible b is guaranteed to minimize the number of parts.
4. Construct the answer using that b.

The challenge is efficiently computing the total capacity for a candidate b.

For a part index a, the suffix length is:

len("<a/b>") = len(a) + len(b) + 3

The available content space becomes:

limit - (len(a) + len(b) + 3)

If any part has non-positive capacity, that candidate b is invalid.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Repeatedly recomputes capacities inefficiently
Optimal	O(n log n)	O(n)	Enumerates part counts efficiently and constructs answer once

Algorithm Walkthrough

1. Let n be the length of the message.
2. Enumerate the possible number of parts b starting from 1.
3. For each candidate b, compute:

• digits_b = len(str(b))
• For every part index a from 1 to b:

available = limit - (len(a) + digits_b + 3)

This represents how many message characters can fit into that part. 4. If available <= 0 for any part, then this b is impossible because even the suffix alone consumes the entire limit. 5. Sum all available capacities across the b parts. 6. If the total capacity is at least the message length, then this is the smallest feasible number of parts. Stop searching. 7. Construct the answer:

• Maintain a pointer into the message.

• For each part a:

• Compute the suffix.

• Compute available content size.

• Take the next chunk of message characters.

• Append the suffix.

8. Return the constructed list.
9. If no valid b is found, return an empty array.

Why it works

The algorithm works because we enumerate possible total part counts in increasing order. The first valid b therefore guarantees the minimum number of parts.

For a fixed b, every suffix is uniquely determined, which means every part's capacity is also uniquely determined. By checking whether the combined capacities can store the full message, we correctly determine feasibility.

Constructing the parts sequentially ensures that concatenating all content segments reconstructs the original message exactly.

Python Solution

from typing import List

class Solution:
    def splitMessage(self, message: str, limit: int) -> List[str]:
        n = len(message)

        for total_parts in range(1, n + 1):
            digits_total = len(str(total_parts))
            total_capacity = 0

            # Calculate total usable capacity
            for part_index in range(1, total_parts + 1):
                digits_index = len(str(part_index))
                available = limit - (digits_index + digits_total + 3)

                if available <= 0:
                    total_capacity = -1
                    break

                total_capacity += available

            if total_capacity < n:
                continue

            result = []
            pointer = 0

            # Construct the actual parts
            for part_index in range(1, total_parts + 1):
                suffix = f"<{part_index}/{total_parts}>"
                available = limit - len(suffix)

                chunk = message[pointer:pointer + available]
                pointer += len(chunk)

                result.append(chunk + suffix)

            return result

        return []

The implementation follows the algorithm directly.

The outer loop enumerates possible numbers of parts. For each candidate value, we calculate the total available capacity by subtracting suffix lengths from the limit.

If any suffix leaves zero or negative room for message content, we immediately reject that candidate.

Once a feasible number of parts is found, we build the answer sequentially. The pointer variable tracks how many characters from the original message have already been consumed.

Because we stop at the first feasible solution, the returned result uses the minimum possible number of parts.

Go Solution

package main

import "strconv"

func splitMessage(message string, limit int) []string {
	n := len(message)

	for totalParts := 1; totalParts <= n; totalParts++ {
		digitsTotal := len(strconv.Itoa(totalParts))
		totalCapacity := 0
		valid := true

		// Calculate total usable capacity
		for partIndex := 1; partIndex <= totalParts; partIndex++ {
			digitsIndex := len(strconv.Itoa(partIndex))
			available := limit - (digitsIndex + digitsTotal + 3)

			if available <= 0 {
				valid = false
				break
			}

			totalCapacity += available
		}

		if !valid || totalCapacity < n {
			continue
		}

		result := make([]string, 0, totalParts)
		pointer := 0

		// Construct the parts
		for partIndex := 1; partIndex <= totalParts; partIndex++ {
			suffix := "<" + strconv.Itoa(partIndex) + "/" +
				strconv.Itoa(totalParts) + ">"

			available := limit - len(suffix)

			end := pointer + available
			if end > n {
				end = n
			}

			chunk := message[pointer:end]
			pointer = end

			result = append(result, chunk+suffix)
		}

		return result
	}

	return []string{}
}

The Go implementation closely mirrors the Python version.

Go requires explicit integer-to-string conversion using strconv.Itoa. Since Go strings are immutable UTF-8 byte sequences, slicing works efficiently here because the input only contains lowercase English letters and spaces, which are all single-byte characters.

The implementation returns an empty slice when no valid split exists.

Worked Examples

Example 1

message = "this is really a very awesome message"
limit = 9

We test increasing values of b.

For smaller values, the total capacity is insufficient.

Eventually:

b = 14

Now:

len("14") = 2

The first nine parts have one-digit indices.

Their suffixes look like:

<1/14>

Length:

1 + 2 + 3 = 6

So each of those parts can store:

9 - 6 = 3

The remaining parts have two-digit indices.

Their suffixes look like:

<10/14>

Length:

2 + 2 + 3 = 7

So they can store:

9 - 7 = 2

The constructed result becomes:

Part	Content	Suffix	Final String
1	thi	<1/14>	thi<1/14>
2	s i	<2/14>	s i<2/14>
3	s r	<3/14>	s r<3/14>
4	eal	<4/14>	eal<4/14>
5	ly	<5/14>	ly <5/14>
6	a v	<6/14>	a v<6/14>
7	ery	<7/14>	ery<7/14>
8	aw	<8/14>	aw<8/14>
9	eso	<9/14>	eso<9/14>
10	me	<10/14>	me<10/14>
11	m	<11/14>	m<11/14>
12	es	<12/14>	es<12/14>
13	sa	<13/14>	sa<13/14>
14	ge	<14/14>	ge<14/14>

Example 2

message = "short message"
limit = 15

Try:

b = 1

Suffix:

<1/1>

Length:

5

Available space:

15 - 5 = 10

The message length is 13, so one part is insufficient.

Now try:

b = 2

Suffix length:

5

Available space per part:

10

Total capacity:

20

Enough to hold the message.

Construction:

Part	Content	Final String
1	short mess	short mess<1/2>
2	age	age<2/2>

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	We test candidate part counts and compute digit lengths repeatedly
Space	O(n)	Output storage dominates memory usage

The time complexity comes from enumerating possible numbers of parts and computing capacities for each candidate. The digit length computations introduce logarithmic factors. Since the message length is at most 10^4, this approach performs comfortably within limits.

The space complexity is linear because the final split message itself may contain O(n) total characters.

Test Cases

solution = Solution()

# Provided examples
assert solution.splitMessage(
    "this is really a very awesome message", 9
) == [
    "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>"
]  # official example

assert solution.splitMessage(
    "short message", 15
) == [
    "short mess<1/2>",
    "age<2/2>"
]  # official example

# Single character message
assert solution.splitMessage("a", 6) == [
    "a<1/1>"
]  # smallest valid message

# Impossible case
assert solution.splitMessage("abc", 5) == []  # suffix leaves no room

# Exact fit in one part
assert solution.splitMessage("hello", 10) == [
    "hello<1/1>"
]  # exactly fills limit

# Multiple parts with changing digit counts
result = solution.splitMessage("abcdefghij" * 20, 12)
assert len(result) > 9  # ensures transition into two-digit indices

# Very small limit but still possible
assert solution.splitMessage("abc", 6) == [
    "a<1/3>",
    "b<2/3>",
    "c<3/3>"
]  # minimum usable capacity

# Large message stress test
large_message = "a" * 10000
result = solution.splitMessage(large_message, 20)

# Verify reconstruction
reconstructed = "".join(
    part[:part.index("<")]
    for part in result
)

assert reconstructed == large_message  # correctness under maximum size

Test Summary

Test	Why
Official example 1	Validates multi-digit suffix handling
Official example 2	Validates normal multi-part split
Single character message	Smallest valid input
Impossible case	Confirms empty array behavior
Exact fit in one part	Tests boundary capacity
Changing digit counts	Ensures suffix growth handled correctly
Very small limit	Tests minimal feasible capacity
Large stress test	Validates performance and reconstruction correctness

Edge Cases

One important edge case occurs when the suffix itself consumes the entire limit. For example, if limit = 5, then even the smallest suffix "<1/1>" already has length 5. This leaves no room for message characters. A naive implementation might accidentally allow empty content segments, but the correct behavior is to return an empty array. The implementation handles this by rejecting any candidate where available capacity is less than or equal to zero.

Another tricky case happens when the number of digits in the part indices changes. For example, moving from part 9 to part 10 increases suffix length by one character. This reduces the available message capacity for later parts. An incorrect implementation might assume all parts have identical capacity. The solution correctly recomputes capacity individually for every part index.

A third important edge case involves exact boundary fits. Sometimes the message length exactly equals the total available capacity. In these situations, every part except possibly the last must still satisfy the limit constraint exactly. The implementation carefully slices only the available number of characters for each part, ensuring that all generated strings remain valid.

Finally, very large messages stress both correctness and efficiency. Since the constraints allow message lengths up to 10^4, inefficient string operations or repeated recomputation could become problematic. The solution avoids unnecessary overhead by stopping immediately once the smallest feasible number of parts is found.