JavaScriptの文字列内のすべての可能なパリンドロームサブシーケンスをカウントする

パリンドロームシーケンス：

文字列シーケンスは、前面と背面から同じものを読み取る場合、パリンドロームシーケンスと呼ばれます。たとえば、「aba」、「madam」、「did」はすべて有効な回文配列です。

最初で唯一の引数として文字列を受け取るJavaScript関数を作成する必要があります。入力として使用される文字列は、「a」、「b」、「c」、および「d」のみで構成されることが保証されています。この関数は、文字列に表示されるすべての連続または非連続の回文サブシーケンスの数をカウントして返す必要があります。

例-

入力文字列が-

const str = 'bccb';

その場合、出力は-

const output = 6;

ここでの回文文字列は「b」、「c」、「bb」、「cc」、「bcb」、「bccb」であるため

例

このためのコードは-

const str = 'bccb';
const countPalindromes = (str = '') => {
   let base = 1000000007;
   const dp = Array(str.length).fill([]);
   for (let l = 1; l <= str.length; l ++) {
      for (let i = 0; i + l - 1 < str.length; i ++) {
         let j = i + l - 1;
         if (l === 1) {
            dp[i][j] = 1;
            continue;
         }
         if (l === 2) {
            dp[i][j] = 2;
            continue;
         }
         if (str[i] === str[j]) {
            let left = i + 1, right = j - 1;
            while (left <= right && str[left] != str[i]) {
               left ++;
            }
            while (left <= right && str[right] != str[i]) {
               right --;
            }
            if (left > right) {
               dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
            }
            else if (left === right) {
               dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
            } else {
               dp[i][j] = dp[i + 1][j - 1] * 2 - dp[left + 1][right - 1];
            }
         } else {
            dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1];
         }
         dp[i][j] = dp[i][j] < 0? dp[i][j] + base : dp[i][j] % base;
      }
   }
   return dp[0][str.length - 1];
};
console.log(countPalindromes(str));

出力

そして、コンソールの出力は-

6