Given a sequence of characters, find the longest palindromic sub-sequence. A sub-sequence is any sequence that can be formed by removing 0 or more characters from the given sequence. For example, the possible sub-sequences for ABC are:

1
2
3
4
5
6
7
8
9
10
ABC
BC
C
B
AC
C
A
AB
B
A

Removing the duplicates you have:

1
2
3
4
5
6
7
ABC
AC
A
BC
B
CD
C

We can calculate all the sub-sequences using this code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function sub(word) {
    var seq = [word];

    if (word.length === 1) {
        return seq;
    }

    for (var i = 0; i < word.length; i++) {
        seq = seq.concat(
            sub(
                word.substring(0, i) + word.substring(i + 1, word.length)
            )
        );
    }

    return seq;
}

The problem with this code is that it has an exponential time complexity and it calculates sub-sequences more than once. We can make this a little more efficient avoiding duplicates:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function sub(sequence) {
    var sequences = {};

    function doIt(word) {
        sequences[word] = true;

        if (word.length === 1) {
            return;
        }

        var s;
        for (var i = 0; i < word.length; i++) {
            s = word.substring(0, i) + word.substring(i + 1, word.length);
            // Only calculate subsequences if they haven't already been calculated
            if (!sequences[s]) {
                doIt(s);
            }
        }
    }

    doIt(sequence);

    return sequences;
}

Because an object(hasmap) is used to keep a record of the sub-sequences that have already been calculated we avoid duplicate work. We can now incorporate a function to check if the sub-sequence is a palindrome:

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
function palindromicSubsequence(sequence) {
    var sequences = {};
    var largestPalindrome = '';

    function isPalindrome(word) {
        var left = 0;
        var right = word.length - 1;

        while (left < right) {
            if (word[left] !== word[right]) {
                return false;
            }
            left++;
            right--;
        }

        return true;
    }

    function sub(word) {
        // If the largest palindrome is already larger than this word then there
        // is no point on continuing on this path
        if (largestPalindrome.length >= word.length) {
            return;
        }

        if (isPalindrome(word)) {
            largestPalindrome = word;
        }
        sequences[word] = true;

        if (word.length === 1) {
            return;
        }

        var s;
        for (var i = 0; i < word.length; i++) {
            s = word.substring(0, i) + word.substring(i + 1, word.length);
            // Only calculate subsequences if they haven't already been calculated
            if (!sequences[s]) {
                sub(s);
            }
        }
    }

    sub(sequence);

    return largestPalindrome;
}

Iā€™m not really sure about the complexity of this algorithm but it should be a lot faster than the previous version.

There is another option that takes O(n^2) that makes use of these observations:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
If the sequence is represented as W[0, n-1] and the largest palindrome is represented as L[0, n-1]

L[i, i] is always 1
Every single character is a palindrome

if (W[0] !== W[n-1]) then L[0, n-1] = max(L[0, n-2], L[1, n-1])
If the first and last characters are not the same then the
longest palindrome is the longest palindrome of the characters
0 to n-2 or 1 to n-1

if (W[0] === W[n-1]) and n === 2 then the result is 2
If the first and last characters are the same and the
word is two letter long then the result is 2

if (W[0] === W[n-1]) and n > 2 then L[0, n-1] = L[1, n-2] + 2
If the first and last characters are the same then
the longest palindrome is 2 + L[1, n-2]

Using these observations we can write a faster program:

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
function ps(sequence) {
    var found = {};

    function doIt(word) {
        function max(l, r) {
            return l > r ? l : r;
        }

        if (word.length === 1) {
            return 1;
        }

        // If this word has already been calculated don't do it again
        if (found[word]) {
            return found[word];
        }

        var res;
        if (word[0] !== word[word.length - 1]) {
            res =  max(ps(word.substring(1)), ps(word.substring(word.length -1, -1)));
        } else {
            if (word.length === 2) {
                res = 2;
            } else {
                res = ps(word.substring(1, word.length -1)) + 2;
            }
        }

        found[word] = res;
        return res;
    }

    return doIt(sequence);
}

According to a test in JSPerf, this last option is about 20 times faster.

[ computer_science  algorithms  javascript  programming  ]
Sorting algorithms computer_science algorithms javascript programming
Raft for reaching consensus computer_science algorithms
The Rabin-Karp algorithm computer_science algorithms javascript programming
House painting problem computer_science algorithms javascript programming
Bitwise operations in Javascript algorithms javascript programming