JavaScript Program to Count Palindromic Substrings
To count palindrome substrings in a string in JavaScript we can use various methods, we will see two approaches to counting palindromic substrings in JavaScript dynamic programming and recursion.
It explores efficient algorithms to determine the total number of palindromic substrings in a given string.
Examples:
Input: str = "abaab"
Output: 3
Explanation: All palindrome substring are: "aba", "aa" , "baab"
Input: str = "abbaeae"
Output: 4
Explanation: All palindrome substring are: "bb", "abba" ,"aea","eae"
Use the below approaches to count palindromic substrings:
Table of Content
- Using Dynamic Programming
- Using Recursion
Using Dynamic Programming
In this approach, we use a 2D array dp
to store whether substrings are palindromes or not. First we iterate over the string, marking single characters and adjacent characters as palindromes. Then, we iterate over substrings of length 3 or more, checking if the substring is a palindrome and updating the count accordingly.
Example: Program to count palindromic substrings using Dynamic Programming.
function countPalindromicSubstrings(str) {
const n = str.length;
let dp = new Array(n).fill()
.map(() => new Array(n).fill(0));
let totalPalindromes = 0;
// Palindromes of single length
for (let i = 0; i < n; i++)
dp[i][i] = 1;
// Palindromes of length 2
for (let i = 0; i < n - 1; i++) {
if (str[i] === str[i + 1]) {
dp[i][i + 1] = 1;
totalPalindromes++;
}
}
// Palindromes of length greater than 2
for (let len = 3; len <= n; len++) {
for (let i = 0; i < n - len + 1; i++) {
let j = i + len - 1;
if (str[i] === str[j] && dp[i + 1][j - 1]) {
dp[i][j] = 1;
totalPalindromes++;
}
}
}
return totalPalindromes;
}
let str = "abaab";
console.log(countPalindromicSubstrings(str));
Output
3
Time Complexity: O(n2)
Auxiliary Space: O(n2)
Using Recursion
In this approach, we recursively check whether each substring is a palindrome, memoizing the results to avoid repeating calculations. The nested loops iterate over all possible substrings to count all palindromic substrings.
Example: Program to count palindromic substrings using a memoized version of recursion.
let dp = Array(1001).fill().map(() =>
Array(1001).fill(-1));
function isPalindrome(s, i, j) {
if (i > j) return 1;
if (dp[i][j] !== -1) return dp[i][j];
// If first and last characters of substring are unequal
if (s[i] !== s[j]) return dp[i][j] = 0;
// Memoization
return dp[i][j] = isPalindrome(s, i + 1, j - 1);
}
function countSubstrings(s) {
const n = s.length;
let count = 0;
// Nested loops to check for all palindromic substrings
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
// Increment count for every palindrome
if (isPalindrome(s, i, j)) count++;
}
}
// Return total palindromic substrings
return count;
}
let s = "abbaeae";
console.log(countSubstrings(s));
Output
4
Time Complexity: O(n3)
Auxiliary Space: O(n2)