Problem 15-2 Longest palindrome subsequence (LPS).

This problem is taken from the book Introduction to Algorithms, Third Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein:

A palindrome is a nonempty string over some alphabet that reads the same forward and backward. Examples of palindromes are all string of length 1, civic, racecar and aibohphobia (fear of palindromes).
Give an efficient algorithm to find the longest palindrome that is a subsequence of a given input string. For example, given the input character, your algorithm should return carac. What is the running time of your algorithm? 

Optimal substructure of an LPS:

Let $({\alpha }_0, {\alpha }_1, {\alpha }_2, ..., {\alpha }_{n-1})$ be the input string.
We define $l(i,j) for 0\le i\le j<n$ the LPS length of the substring from ${\alpha }_i$ to ${\alpha }_{\mathrm{j.}}$

• If $i=j$ then $l(i,j)=1$.
• If ${\alpha }_i={\alpha }_j \wedge i\ne j$ then $l(i,j) = l(i+1,j-1)+2$.
• If ${\alpha }_i\ne {\alpha }_j$ then $l(i,j)=l(i+1,j) or l(i,j)=l(i,j-1)$

The running time of my algorithm is $\Theta \left(n^2\right)$.

My solution using a bottom-up approach: 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

enum direction { vertical, horizontal, diagonal }; template<typename T> using matrix = std::vector<std::vector<T>>; void longest_palindrome_fill_tables(const std::string& input, matrix<int> &lengths, matrix<direction> &path) { int N = input.length(); for (int i = 0; i < N; ++i) { lengths[i][i] = 1; } for (int range = 2; range <= N; ++range) { for (int i = 0, to = N - range + 1; i < to; ++i) { int j = i + range - 1; if (input[i] == input[j]) { path[i][j] = diagonal; lengths[i][j] = lengths[i + 1][j - 1] + 2; } else if (lengths[i][j - 1] > lengths[i + 1][j]) { path[i][j] = vertical; lengths[i][j] = lengths[i][j - 1]; } else { path[i][j] = horizontal; lengths[i][j] = lengths[i + 1][j]; } } } } void generate_palindrome(int i, int j , const matrix<direction>& paths, const std::string &input, std::deque<char> &palindrome) { if (i > j) { return; } if (i == j) { return palindrome.push_front(input[j]); } switch (paths[i][j]) { case diagonal: generate_palindrome(i + 1, j - 1, paths, input, palindrome); palindrome.push_back(input[j]); return palindrome.push_front(input[j]); case vertical: return generate_palindrome(i, j - 1, paths, input, palindrome); case horizontal: generate_palindrome(i + 1, j, paths, input, palindrome); } } std::string longest_palindrome(const std::string& input) { int N = input.length(); matrix<int> lengths(N, std::vector<int>(N, 0)); matrix<direction> paths(N, std::vector<direction>(N, diagonal)); std::deque<char> palindrome; longest_palindrome_fill_tables(input, lengths, paths); generate_palindrome(0, N - 1, paths, input, palindrome); return std::string(palindrome.begin(), palindrome.end()); }