333435363738

class Solution {
    // Check if substring s[start...end] is palindrome
    isPalindrome(s, start, end) {
        // Compare characters from both ends moving towards center
        while (start < end) {
            if (s[start] !== s[end])
                return false;
            start++;
            end--;
        }
        return true;
    }

    // Count all palindromic substrings using brute force
    countPalindromicSubstrings(s) {
        const n = s.length;
        let count = 0;

        // Generate all possible substrings of s
        for (let start = 0; start < n; start++) {
            for (let end = start; end < n; end++) {
                // Check if current substring is palindrome
                if (this.isPalindrome(s, start, end))
                    // Increment count if palindrome
                    count++;  
            }
        }
        return count;
    }
}

// Driver code
const s = "abba";
const sol = new Solution();

// Print total count of palindromic substrings
console.log("Number of palindromic substrings:", sol.countPalindromicSubstrings(s));

Complexity Analysis

Time Complexity: O(N^3), we use nested loops to generate all the substirngs and for every substring we check whether its a palindrome or not.
Space Complexity: O(1), constant additional space is used.

Optimal Approach

Algorithm

To optimize our solution, we can use dynamic programming to avoid redundant checking of palindromic substrings. We can construct our DP table by following these steps:

Initialize a 2D boolean DP table dp[n][n], where dp[i][j] indicates if substring from index i to j is a palindrome.
All substrings of length 1 are palindromes, so set dp[i][i] as true for all i, and initialize the count accordingly.
Check all substrings of length