[LCS] Solve in O(n) space.
[String] Zigzag output sequence.
[DP] Break words.