# AI solution for JavaScript Coding Question on BFE.dev

111. Count palindromic substrings

One possible solution for counting palindromic substrings:

`function countPalindromes(s) { let count = 0; for(let i = 0; i < s.length; i++) { for(let j = i+1; j <= s.length; j++) { const subStr = s.substring(i, j); if(isPalindrome(subStr)) { count++; } } } return count;}function isPalindrome(str) { const reverse = str.split('').reverse().join(''); return str === reverse;}`

The `countPalindromes`

function simply loops over all possible substrings of the input string `s`

, and for each substring, it checks if it is a palindrome using the `isPalindrome`

function.

The time complexity of this solution is O(n^3) because of the three nested loops: one to loop over all starting positions, one to loop over all ending positions, and another one to check if each substring is a palindrome. The space complexity is O(1) because we only need some constant extra memory to store the `count`

variable.

To improve the time complexity, we can use a dynamic programming approach. We can create a 2D array `dp`

where `dp[i][j]`

is true if the substring from index `i`

to index `j`

is a palindrome. We can then fill this array bottom-up, starting from all substrings of length 1 (which are palindromes), and then moving up to longer substrings. The number of palindromes is simply the number of `true`

values in this array.

Here's the improved solution:

`function countPalindromes(s) { let count = 0; const n = s.length; const dp = Array.from(Array(n), () => Array(n).fill(false)); // all substrings of length 1 are palindromes for(let i = 0; i < n; i++) { dp[i][i] = true; count++; } // check substrings of length 2 for(let i = 0; i < n-1; i++) { if(s[i] === s[i+1]) { dp[i][i+1] = true; count++; } } // check longer substrings for(let len = 3; len <= n; len++) { for(let i = 0; i < n-len+1; i++) { const j = i+len-1; if(s[i] === s[j] && dp[i+1][j-1]) { dp[i][j] = true; count++; } } } return count;}`

This solution has a time complexity of O(n^2) because we need to fill in the `dp`

array of size n^2, and the space complexity is O(n^2) as well. However, we can optimize the space complexity to O(n) by using just one array for the `dp`

values of the current row and the previous row. Here's the optimized solution:

`function countPalindromes(s) { let count = 0; const n = s.length; let dp = Array(n).fill(false); // all substrings of length 1 are palindromes for(let i = 0; i < n; i++) { dp[i] = true; count++; } // check substrings of length 2 for(let i = 0; i < n-1; i++) { if(s[i] === s[i+1]) { dp[i] = dp[i+1] = true; count++; } } // check longer substrings for(let len = 3; len <= n; len++) { let prev = dp[0]; dp[0] = false; // reset first cell for(let i = 1; i < n-len+2; i++) { // skip last few cells const j = i+len-2; const temp = dp[i]; if(s[i-1] === s[j] && prev) { dp[i] = true; count++; } else { dp[i] = false; } prev = temp; } } return count;}`

The idea here is to use just one array `dp`

to store the values for the current row and the previous row. We still start by initializing all substrings of length 1 to be palindromes, and all substrings of length 2 to be palindromes if both characters are the same. Then, we loop over all longer substrings, and for each substring, we compare the two characters at the ends, and if they are the same, and the substring inside them is also a palindrome (i.e., `dp[i+1][j-1]`

is true), then we set `dp[i][j]`

to be true, and increment the `count`

. Finally, we move to the next row by copying the current `dp`

values to `prev`

, and resetting the first cell of `dp`

to false.

This optimized solution still has a time complexity of O(n^2), but with a space complexity of only O(n).