DYNAMIC PROGRAMMING · CORE

String partition DP

Cut a string or sequence into pieces that follow a rule, by deciding for each position whether the text up to it can end a piece.

Time O(n³)Space O(n)6 practice problemsStep-through picture

The idea

Many problems ask you to cut a string into pieces: split "darkmode" into dictionary words, break a paragraph into lines, or cut a label into palindromes. The DP state is a position in the string, and the question is about the text before that position.

Cell ok[end] answers "can the first end characters be cut into valid pieces?" To fill it, try every place start where the last piece could begin. If the text before start can be cut (ok[start]) and the last piece text.slice(start, end) is valid, then ok[end] is true.

The same shape gives counts (add instead of "or"), fewest pieces (take the minimum), or the cheapest layout (add a cost per piece).

An everyday example

Reading a hashtag

A hashtag like #darkmodetips has no spaces, so you read it from the left and mark every spot where a word could end. "dark" is a word, so you mark the spot after k. From that mark, "mode" is a word, so you mark the spot after e. From there, "tips" reaches the end. If the end gets a mark, the whole tag can be read as words.

How the example maps to the code
In the example	In the code
The tag without spaces	`text`
A mark at a spot where a word could end	`ok[end] = true`
Where the last word starts	`start`
The last word itself	`text.slice(start, end)`
Your list of known words	`dictionary`, a `Set`

From the slow way to string partition dp

Start with brute force: try every way to cut the text into pieces, and check whether every piece is a word. A text of n characters has n - 1 places to cut, and each is cut or not, so there are 2^(n - 1) ways. For 30 characters that is 536,870,912 ways.
A recursive search does better: find a word at the start, then solve the rest. But it asks the same question many times. In a text like "aaaaaaaab", many different first cuts all lead to "can the text from position 5 be split?". The answer only depends on the position, not on how you got there.
So flip it around and ask about the beginning of the text. Let ok[end] mean "the first end characters can be cut into words". The last piece of such a cut starts at some start, the text before it must be cuttable (ok[start]), and the piece text.slice(start, end) must be a word.
There are n + 1 positions, so the table is small. Set ok[0] = true for the empty start, then for each end from left to right, try every start before it and stop at the first that works. The last cell is the answer. That loop is string partition DP.

How it works

Put the allowed words in a Set called dictionary, so each check is fast.
Make ok with text.length + 1 cells, all false. ok[k] is about the first k characters.
Set ok[0] = true: the empty start of the string needs no pieces.
For each end from 1 to text.length, try every start before it.
If ok[start] is true and text.slice(start, end) is in the dictionary, set ok[end] = true and stop trying.
Return ok[text.length].

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…

See every step at onceThe same run, laid out side by side

Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor

function canSplit(text, words) {
const dictionary = new Set(words);
const ok = new Array(text.length + 1).fill(false);
ok[0] = true;
for (let end = 1; end <= text.length; end++) {
for (let start = 0; start < end; start++) {
if (ok[start] && dictionary.has(text.slice(start, end))) {
ok[end] = true;
break;
}
}
}
return ok[text.length];
}

How fast it is

Time	`O(n³)`
Extra memory	`O(n)`

About n²/2 pairs of start and end, and each slice copies up to n characters. Limiting start to the longest word length makes it much faster in practice.

Best caseO(n²)
Every prefix is itself a word, like "aaaa" with ["a", "aa", "aaa", "aaaa"]: each end succeeds at start = 0, but the slice and its hash still cost up to end characters.
Average caseO(n³)
A typical text where most end values try many starts before one works or all fail, and each slice copies its characters.
Worst caseO(n³)
No split exists until the end, like "aaaaaaab" with ["a", "aa"]: almost every end tries almost every start, and each slice copies up to n characters.

Common mistakes

Using greedy longest-match: taking the longest word at each point. For "darkmode" with darkmod in the list, greedy can get stuck. Try every start.
Recursing on every possible cut without saving answers, which takes exponential time on inputs like "aaaaaaaab".
Sizing the table text.length instead of text.length + 1. There is one more position than there are characters.
Forgetting ok[0] = true, so nothing ever becomes true.

When to use it

Look for these clues in a problem:

A string must be cut into pieces, and each piece must follow a rule (in a dictionary, a palindrome, short enough to fit a line).
The question asks whether a split exists, how many splits exist, or the split with the fewest pieces or least cost.
Trying every way to cut a string of length n would mean 2^(n - 1) options.
Checking one piece is easy, but choosing where to cut is the hard part.

Check yourself

Answer each one in your head first, then open it.

Why is ok[0] true?

It stands for the empty beginning of the text, which needs no pieces. Without it, no first word could ever be accepted.

Why does ok have text.length + 1 cells?

Its index is a position between characters, from before the first to after the last. A text of n characters has n + 1 such positions.

In the trace, why didn't ok[6] being true lead to the answer?

The text after position 6 is op, and no word in the list matches it or any of its prefixes. The answer comes from position 5 instead.

Is the break needed for correctness?

No. It only saves time: once one start works, ok[end] is true, and more starts can't change that.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

0 of 6 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

#547Split a Hashtag Into Known Words

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The table keeps one promise: when the loop starts on end, each ok[k] for k < end is true exactly when the first k characters can be cut into words. ok[0] = true is right, since the empty text needs no pieces.

Filling ok[end] keeps the promise. If the first end characters can be cut, look at the last piece of one such cut. It starts at some start, it is a word, and the text before it is a valid cut, so ok[start] is true. The loop tries every start, so it finds one and sets ok[end] to true. And if the code sets ok[end] to true, it found a valid cut for start plus one more word, so the cut really exists. Both directions hold.

Every start is smaller than end, so the left-to-right order only reads finished cells. The break is safe because one valid start is enough to answer yes. After the last end, the promise says ok[text.length] answers the whole question.

Going deeper

3 more ideas

What each cell means

ok[end] is true when the first end characters, text.slice(0, end), can be cut into dictionary words with nothing left over. It does not record how; it only says it is possible. The index is a position between characters, so there are length + 1 cells.

How much work it does

There are n ends and up to n starts for each, and each check slices a piece of up to n characters, so the time is O(n^3) in the worst case and O(n) space. If the longest word has length L, only try starts within L of end, which gives O(n * L^2).

Line breaking is the same shape

To break words into lines of width width, let best[i] be the least total cost to lay out the first i words. For each i, try every j where the last line starts. If words j..i-1 fit on one line, the cost is best[j] plus the cost of that line, such as the square of its unused space. This avoids the greedy layout's ugly, nearly empty lines.

Work it by hand

Every step in a table, with why

Check whether a word can be cut into dictionary words. One early cut leads to a dead end. Each row fills one cell of ok.

text = "tabletop", words = ["tab", "table", "let", "top"]

Step	`end`	`text.slice(0, end)`	Piece found	`ok` true at	What happens	Why
1	1	t	none	0	1 start tried	Only `start = 0` is possible, and `t` is not a word, so `ok[1]` stays false.
2	2	ta	none	0	2 starts tried	`ta` is not a word, and `ok[1]` is false, so `start = 1` is skipped at once.
3	3	tab	`tab` from 0	0, 3	Found at `start = 0`	`ok[0]` is true and `tab` is a word, so `ok[3] = true` and the inner loop breaks.
4	4	tabl	none	0, 3	4 starts tried	From `start = 3`, the piece is `l`, which is not a word.
5	5	table	`table` from 0	0, 3, 5	Found at `start = 0`	The whole prefix is a word. The break skips the other starts.
6	6	tablet	`let` from 3	0, 3, 5, 6	Found at `start = 3`	`tab` + `let` works. This cut will turn out to be a dead end, but the table doesn't need to know that.
7	7	tableto	none	0, 3, 5, 6	7 starts tried	From the good starts 0, 3, 5, and 6, the pieces `tableto`, `leto`, `to`, and `o` are not in the list.
8	8	tabletop	`top` from 5	0, 3, 5, 6, 8	Found at `start = 5`	Starts 0 and 3 fail; `ok[4]` is false, so start 4 is skipped. From 5, `top` is a word. The loop ends and line 13 returns `ok[8]`.

It returns true, for table + top. The cut tab + let also made ok[6] true, but nothing continues from position 6. The table tries both without going back.

Compared with other ways

When to pick something else

Approach	Time	Extra memory	Choose it when
String partition DP	`O(n³)`	`O(n)`	The default for texts up to a few thousand characters.
Partition DP with a word-length limit	`O(n · k²)`	`O(n)`	Long texts with a dictionary of short words; here `k` is the longest word's length.
Partition DP with a trie	`O(n²)`	`O(n)`	Big dictionaries: from each `start` with `ok[start]` true, walk the trie forward one character at a time, marking every word end you reach.
Recursion without saving answers	`O(2^n)`	`O(n)`	Never for real inputs. Texts like `"aaaaaaaab"` make it explore every cut.

Extra memory: O(n) for ok, plus the Set of words, plus one slice at a time.

How the steps grow

String partition DP, Partition DP with a word-length limit O(n³)
Partition DP with a trie O(n²)
Recursion without saving answers O(2^n)

About how many steps for bigger inputs
Approach	n = 10	n = 1,000	n = 1,000,000
String partition DP	1,000	1 billion	more than a quadrillion
Partition DP with a word-length limit	1,000	1 billion	more than a quadrillion
Partition DP with a trie	100	1 million	1 trillion
Recursion without saving answers	1,024	more than a quadrillion	more than a quadrillion

Inputs that need care

5 tricky inputs

An empty text: text = "": ok has one cell, ok[0] = true, and the loop never runs, so it returns true. Decide whether an empty text should count as splittable.
An empty word list: No piece is ever found, so every cell after 0 stays false and it returns false for any non-empty text.
A word used more than once: "tabtab" with ["tab"]: It returns true. The Set is only checked, never changed, so words can repeat.
An empty string in the word list: It is never asked about, because start < end means every slice has at least one character. It can't cause an endless loop here.
Different letter case: "TabLe" with ["tab", "le"]: Set.has is exact, so it returns false. Lowercase the text and the words first if case shouldn't matter.

Variations and follow-ups

Twists interviewers add

Count the ways, or the fewest pieces

To count cuts, store numbers and add ways[start] for every valid start instead of stopping at the first. For the fewest pieces, store Infinity and take pieces[start] + 1 at its smallest. Both remove the break.

List every valid sentence

Keep, for each end, the list of starts that work. Then walk back from text.length to build every sentence. The number of sentences can grow exponentially, so the output itself can be huge; the table only saves the search.

Only try starts near `end`

If the longest word has L characters, any start more than L before end gives a piece that can't be a word. Loop start from end - L only, which gives O(n · L²) time, much faster for long texts.

Fewest cuts into palindromes

With "each piece must read the same backward", the dictionary check becomes a palindrome check. Precompute which slices are palindromes with an interval table, then run the same partition loop with the minimum.

In an interview

Spot it, explain it, answer follow-ups

Spot it from "split the string into pieces that are all valid", "insert spaces to make words", or "fewest cuts so every piece is X".
Say what the index means: ok[end] is about the first end characters, so positions sit between characters and there are n + 1 of them. That avoids the most common off-by-one bug.
Test a text where greedy fails, like a longer word that leads to a dead end and a shorter one that works, plus the empty text and a text with no valid split.
Expect "now return all the sentences". Keep the valid starts for each end and backtrack from the end, and mention that the output itself can be exponential.

Where frontend code uses it

The same idea in real UI code

Splitting hashtags, URL slugs, or camelCase names into words, for search or for screen readers, is this DP.
Languages written without spaces between words, such as Thai, need dictionary-based word splitting for line breaking and double-click selection; browsers rely on libraries like ICU for this.
CSS text-wrap: pretty lets the browser choose line breaks by looking at more than one line at a time, and TeX's line breaker picks breaks for a whole paragraph with this kind of DP.

String partition DP

The idea

An everyday example

Reading a hashtag

From the slow way to string partition dp

How it works

Watch it run

The code

How fast it is

Common mistakes

When to use it

Check yourself

Practice problems

easy

medium

hard

Go further

Why it works

Going deeper

What each cell means

How much work it does

Line breaking is the same shape

Work it by hand

Compared with other ways

How the steps grow

Inputs that need care

Variations and follow-ups

Count the ways, or the fewest pieces

List every valid sentence

Only try starts near `end`

Fewest cuts into palindromes

In an interview

Where frontend code uses it

Tuto

Hi, I'm Tuto

Give feedback

The idea

An everyday example

Reading a hashtag

From the slow way to string partition dp

How it works

Watch it run

The code

How fast it is

Common mistakes

When to use it

Check yourself

Practice problems

easy

medium

hard

Go further

Why it works

Going deeper

What each cell means

How much work it does

Line breaking is the same shape

Work it by hand

Compared with other ways

How the steps grow

Inputs that need care

Variations and follow-ups

Count the ways, or the fewest pieces

List every valid sentence

Only try starts near end

Fewest cuts into palindromes

In an interview

Where frontend code uses it

Related algorithms

Only try starts near `end`