প্যালিনড্রোম সিকোয়েন্স:
একটি স্ট্রিং সিকোয়েন্সকে প্যালিনড্রোম বলা হয় যদি সেটি সামনে থেকে এবং পেছনে থেকে পড়লে একই থাকে। যেমন: '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
