DEV Community

loading...

LeetCode 647. Palindromic Substrings (javascript solution)

codingpineapple
・1 min read

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;
};
Enter fullscreen mode Exit fullscreen mode

Discussion (0)