Word Wrap¶
Split a string at a given width without breaking words, the same line-wrapping logic used when formatting text for terminal UIs or pre-processing input for NLP tokenizers.
Problem¶
Given a string and a character limit, split the text into lines where no line exceeds the limit. Words must not be broken mid-way; if a word doesn't fit on the current line, start a new one.
Input: "The quick brown fox", limit 12
Output: ["The quick", "brown fox"]
Approach¶
- Split the text into words.
- Maintain a running line. For each word, check if appending it (plus a space) would exceed the limit.
- If it fits, append. If not, flush the current line to the result and start a new line with the current word.
- After the loop, flush any remaining text.
This is a single-pass greedy algorithm, no backtracking needed.
Implementation¶
def word_wrap(text, limit):
words = text.split(" ")
lines = []
current = ""
for word in words:
new_len = len(word) if not current else len(current) + len(word) + 1
if new_len > limit:
if current:
lines.append(current)
current = word
else:
current = f"{current} {word}".strip()
if current:
lines.append(current)
return lines
text = "The quick brown fox"
assert word_wrap(text, 12) == ["The quick", "brown fox"]
Complexity¶
- Time: O(n), single pass over all characters
- Space: O(n), storing the output lines
Takeaway¶
Word wrapping is a greedy interval-packing problem. The same pattern shows up when chunking documents for retrieval-augmented generation (RAG), you want to split text at natural boundaries without exceeding a token budget.