Yes, something like that. With the standard algorithm you compute a matix where each entry (i,j) in the matrix gets computed from entries (i-1,j),(i,j-1),(i-1,j

Yes, something like that. With the standard algorithm you compute a matix where each entry (i,j) in the matrix gets computed from entries (i-1,j),(i,j-1),(i-1,j-1). If you compute the matrix row-by-row then you only need to store two rows, because the next row only depends on the current row. You can reduce the cost from storing two rows (2n entries) to one row (n entries) by rewriting it in-place. You're right that you'd store the solution string in a linked list, because they have O(1) non-destructive append. Or maybe there's another smarter and faster scheme than a linked list? Edit: oh, you could just use an array for each column, and append the letter in-place. Or does this use more space because the prefixes are not shared among the different columns?