জাভাস্ক্রিপ্টে একটি স্ট্রিং এর মধ্যে সমস্ত সম্ভাব্য প্যালিনড্রোমিক পরবর্তী সংখ্যা গণনা করা

প্যালিনড্রোম সিকোয়েন্স:

একটি স্ট্রিং সিকোয়েন্সকে প্যালিনড্রোম সিকোয়েন্স বলা হয় যদি এটি সামনে এবং পিছনে একই রকম পড়ে। উদাহরণস্বরূপ, 'aba', 'madam, 'did' হল সব বৈধ প্যালিনড্রোম সিকোয়েন্স।

আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা প্রথম এবং একমাত্র যুক্তি হিসাবে একটি স্ট্রিং নেয়। ইনপুট হিসাবে গৃহীত স্ট্রিং শুধুমাত্র '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