How to write a Javascript function to get all palindromic subsequences from string in order?

Question

A subsequence is a group of characters chosen from a list while maintaining their order. For instance, the subsequenes of the string abc are [a, b, c, ab, ac, bc, abc].

Now, I need to write a function to return all the palindromic subsequences from a given string in order. For instance, for the string acdapmpomp, the output should be [a,c,d,p,m,o,aa,aca,ada,pmp,mm,mom,pp,ppp,pop,mpm,pmpmp].

My code is:

function getAllPalindromicSubsequences(str) {
    var result = [];
    for (let i = 0; i < str.length; i++) {
        for (let j = i + 1; j < str.length + 1; j++) {
            if (str.slice(i, j).split("").reverse().join("") == str.slice(i, j)){
                result.push(str.slice(i, j));
            }
        }
    }
    return result;
}

console.log(getAllPalindromicSubsequences("acdapmpomp"));

But this produces the following output:

[
  'a', 'c', 'd',
  'a', 'p', 'pmp',
  'm', 'p', 'o',
  'm', 'p'
]

What is the mistake I am making? And what should be the correct code?

Your code isn't collecting the subsequences correctly as you're only looking at continuous/connect groups/slices of letters from `i` to `j` — Nick Parsons, Sep 06 '20 at 08:18
The right approach would be using dynamic programming. See [here](https://stackoverflow.com/questions/39746540/dynamic-programming-to-find-all-palindromic-substrings) for instance — Itay, Sep 06 '20 at 08:20

score 2 · Accepted Answer · answered Sep 06 '20 at 08:40

You could take a recursive approach and collect all character and check is they are palindromes.

function getSub(string) {
    function isPalindrome(string) {
        let l = 0,
            r = string.length - 1;

        if (!string) return false;
        while (l < r) {
            if (string[l] !== string[r]) return false;
            l++; r--;
        }
        return true;
    }
    function sub([character, ...rest], right = '') {
        if (isPalindrome(right) && !result.includes(right)) result.push(right);
        if (!character) return;
        sub(rest, right + character);
        sub(rest, right);
    }

    var result = [];
    sub([...string])
    return result;
}

console.log(getSub('acdapmpomp'));

How to write a Javascript function to get all palindromic subsequences from string in order?

1 Answers1