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).