Abstract / Summary

Split a message into parts so each part is at most a given number of letters long.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 42% (50k+ submissions).

Typical patterns to solve this problem:

• Enumeration
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The Solution.splitMessage method receives a text string and a maximum allowed length for each fragment. Its goal is to partition the original text into the smallest possible number of fragments such that every fragment ends with a suffix of the form <i/n> (where i is the 1-based index and n is the total number of fragments) and the total length of each fragment does not exceed limit. If no feasible partition exists, an empty list is returned. The implementation relies on a helper that checks feasibility for a given fragment count, a series of bounded binary searches across digit-length intervals, and a generator that yields the final fragments.

Core Logic

The algorithm first records the total number of characters in message (size). A tuple thresholds defines the boundaries where the number of digits in the total-fragment count changes (0-9, 10-99, 100-999, …).

size = len(message)
thresholds = (0, 10, 100, 1000, 10000, 100000)

Feasibility Test

The nested possible(count) function determines whether the message can be split into exactly count parts. It computes the length of the static part of the suffix ("</count>") and then accumulates how many characters of the original message can be accommodated across all fragments.

def possible(count):
    suffix = 3 + len(str(count))          # length of "</count>"
    done   = 0

    # fast-track for a large range of counts
    while 1200 < count < 10000:
        done  += 100 * (limit - (suffix + 4))
        count -= 100

    # precise brute-force for the remaining count
    digits = 1
    for i in range(1, count + 1):
        if i in (10, 100, 1000, 10000):
            digits += 1
        done += limit - (suffix + digits)
        if done >= size:                  # early success
            return True
    return False

The function first applies a “hacky” acceleration when count lies between 1 200 and 10 000. In that region the number of digits in the index part of the suffix is constant (four digits for the index, plus the digits of count). The loop adds the contribution of 100 fragments at a time, reducing count accordingly. After the fast-track, a precise iteration processes the remaining fragments one by one, adjusting the digit count whenever the index crosses a power of ten. An early exit occurs as soon as the accumulated capacity done meets or exceeds the original message length.

Bounded Binary Searches

Because the suffix length changes when the total number of fragments gains an extra digit, a plain binary search over the entire range can miss feasible solutions. The code therefore iterates over each digit-length interval defined by thresholds. For each interval it performs a binary search using bisect_left with possible as the key function.

for first, last in zip(thresholds, thresholds[1:]):
    best = first + bisect_left(range(first, last), True, key=possible)
    if best < last:
        # construct the fragments
        for i in range(1, best + 1):
            suffix = "<" + str(i) + "/" + str(best) + ">"
            output = limit - len(suffix)
            yield message[:output] + suffix
            message = message[output:]
        return

bisect_left searches the half-open interval [first, last) for the smallest count that makes possible true. If such a count (best) is found inside the interval, the algorithm proceeds to build the final fragments.

Fragment Construction

When a feasible count is identified, the method iterates from 1 to best, builds the appropriate suffix, computes the usable payload length (output), slices the next chunk from message, appends the suffix, yields the completed fragment, and advances the remaining message pointer.

suffix = "<" + str(i) + "/" + str(best) + ">"
output = limit - len(suffix)
yield message[:output] + suffix
message = message[output:]

If none of the intervals yields a feasible count, the function falls through to the final return [], indicating that the message cannot be split under the given limit.

Edge Cases Handled

The implementation explicitly accounts for the change in suffix length when the total fragment count crosses a power of ten. The digits variable inside possible is incremented exactly at the thresholds 10, 100, 1000, 10000, ensuring that the capacity calculation reflects the longer index part of the suffix.

The early-exit condition if done >= size: return True allows the feasibility test to succeed as soon as enough characters have been allocated, even if the loop has not processed all count indices. This covers cases where the remaining fragments would be empty or contain only the suffix.

The fast-track loop for 1200 < count < 10000 handles large counts efficiently, preventing the brute-force iteration from becoming a bottleneck when many fragments are required.

When no feasible partition exists, the method returns an empty list rather than raising an exception, providing a clean failure signal for callers.

Performance Optimizations

The most noticeable optimization is the bulk-addition step inside possible. By processing 100 fragments at a time when the count lies in a range where the suffix length is stable, the algorithm reduces the number of loop iterations dramatically for large count values.

The use of bisect_left with a custom key function replaces a manual binary search implementation and leverages the standard library’s efficient search routine. Because the search is confined to intervals where the suffix digit count is constant, each binary search operates over a monotonic region, guaranteeing correctness while keeping the number of feasibility checks low.

The early-exit check inside the precise loop prevents unnecessary work once the accumulated capacity already covers the entire message. This is particularly beneficial for inputs where the required number of fragments is small relative to the limit, allowing the function to stop after only a few iterations.

Finally, the fragment generation loop slices the original message only once per fragment and reassigns the remaining substring, avoiding the creation of intermediate lists or repeated concatenations. This in-place progression minimizes memory churn during output construction.

Imagine you have a really long story written on a very long piece of paper, but you need to send it in tiny envelopes. Each envelope can only hold a small number of letters, and you have to write a little label on the back of every envelope to show which part of the story is inside and how many envelopes there are in total.

The code is like a clever helper that picks up your long story and decides exactly how to chop it up into smaller pieces so that everything fits perfectly. First, the helper figures out if it needs ten envelopes, a hundred envelopes, or maybe even more. It keeps guessing different numbers of envelopes until it finds the smallest amount that can hold the whole story without breaking the rules about how much space is left for the labels.

Once the helper knows the right number of envelopes, it starts cutting the story into chunks. It creates a special label for each piece, like saying this is piece one of ten, piece two of ten, and so on. It carefully puts each chunk into an envelope with its label, moves the rest of the story along, and keeps going until every single word of the story has found a home in its own labeled envelope. If the story is just too long or the envelopes are too small to fit the labels, the helper realizes it cannot be done and stops.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java		Python	TS
	WalkCCC	C++		Java		Python
	leetcode.ca	C++		Java	Go	Python
	Progiez	C++		Java		Python
github	charles-wangkai			Java
	fsq	C++
	JoshCrozier		JS
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality