LeetCode 647. Palindromic Substrings (javascript solution)

#algorithms #javascript

Description:

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Solution:

Time Complexity : O(n^2)
Space Complexity: O(n^2)

var countSubstrings = function(s) {
    const n = s.length;
    const dp = [...Array(n)].map(() => Array(n).fill(false));
    let count = 0;
    // Base case: single letter substrings
    for(let i = 0; i < n; i++) {
        dp[i][i] = true;
        count++
    }

    // Base case: double letter substrings
    for(let i = 0; i < n-1; i++) {
        dp[i][i+1] = (s[i] === s[i+1]);
        dp[i][i+1] && count++;
    }

    // substrings longer than 2 chars
    for(let len = 3; len <= n; len++) {
        let start = 0, end = start+len-1;

        while(end < n) {
            dp[start][end] = (dp[start+1][end-1] && s[start] === s[end]);
            dp[start][end] && count++;
            start++; end++;
        }
    }
    return count;
};