One-dimensional Dynamic Programming
Growing outward from a center
Two problems where the obvious table is beaten by something simpler.
Key idea
Grow from the middle
A stretch reading the same both ways has a center, and every longer one containing it also contains that center. So rather than testing every stretch, stand at each possible center and expand outward while the ends match.
That finds every such stretch, because each one is found exactly once from its own center.
Why it works
There are two kinds of center
An odd-length stretch centers on a character. An even-length one centers between two characters. A string of length n therefore has 2n minus 1 possible centers, and missing the even ones is the classic error.
The usual shape runs one expansion per character and one per gap, or equivalently loops over all 2n minus 1 centers and derives the two starting indexes arithmetically.
Tip
Counting by hand on a tiny string
Do this once on a three-character string. abc has three single characters and nothing longer, so three in total. aaa has three singles, two adjacent pairs, and the whole string, so six.
That second count is what confirms both center kinds are covered. A longer test case would not distinguish the two failure modes nearly as clearly, which is why the smallest interesting input is the one to check first.
Key idea
The same expansion, different reading
To find the longest rather than count them, track the best length and its starting index during the same expansions, then slice once at the end.
Returning the string from every expansion that improves the record allocates repeatedly for no reason. Track two integers and slice once, which is the same advice as the minimum-window lesson in Unit 3.
Tip
The table version exists and is worse
There is a standard O(n squared) table where each cell says whether the stretch between two positions is mirrored, filled by increasing length. It is a fine answer and it uses O(n squared) space.
Center expansion is also O(n squared) time and uses O(1) space. When two solutions share a time bound and one uses far less memory, the simpler one is the better answer, and being able to say why is worth more than knowing both.
Cost
Cost
There are about 2n centers and each expansion can run up to n steps, so O(n squared) time and O(1) extra space.
There is an O(n) algorithm for this problem. It is intricate, rarely expected, and worth naming only if the constraints make quadratic impossible, which for these problems they do not.
Predict the output: only odd centers
This expands from character centers only and never from the gaps between them. Type the two values it prints.
Palindromic Substrings
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.
Longest Palindromic Substring
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.