Palindromic Substrings - LeetCode Daily Challenge

Problem Statement

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Example 1

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Try here before watching the video.

Video Solution

Java Code

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        if(n == 1) return 1;

        boolean[][] dp = new boolean[n][n];
        int countOfPalindromes = 0;

        // one length
        for(int i = 0; i < n; i++) {
            dp[i][i] = true;
            countOfPalindromes += 1;
        }

        // two length
        for(int i = 0; i < n - 1; i++) {
            if(s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                countOfPalindromes += 1;
            }
        }

        for(int length = 3; length <= n; length++) {
            for(int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if(s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    countOfPalindromes += 1;
                }
            }
        }

        return countOfPalindromes;
    }
}

C++ Code

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.length();
        if (n == 1) return 1;

        vector<vector<bool>> dp(n, vector<bool>(n, false));
        int countOfPalindromes = 0;

        // one length
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
            countOfPalindromes += 1;
        }

        // two length
        for (int i = 0; i < n - 1; i++) {
            if (s[i] == s[i + 1]) {
                dp[i][i + 1] = true;
                countOfPalindromes += 1;
            }
        }

        for (int length = 3; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if (s[i] == s[j] && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    countOfPalindromes += 1;
                }
            }
        }

        return countOfPalindromes;
    }
};

Python Code

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        if n == 1:
            return 1

        dp = [[False] * n for _ in range(n)]
        countOfPalindromes = 0

        # one length
        for i in range(n):
            dp[i][i] = True
            countOfPalindromes += 1

        # two length
        for i in range(n - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = True
                countOfPalindromes += 1

        for length in range(3, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j] and dp[i + 1][j - 1]:
                    dp[i][j] = True
                    countOfPalindromes += 1

        return countOfPalindromes

Javascript Code

var countSubstrings = function(s) {
    const n = s.length;
    if (n === 1) return 1;

    const dp = Array.from(Array(n), () => Array(n).fill(false));
    let countOfPalindromes = 0;

    // one length
    for (let i = 0; i < n; i++) {
        dp[i][i] = true;
        countOfPalindromes += 1;
    }

    // two length
    for (let i = 0; i < n - 1; i++) {
        if (s[i] === s[i + 1]) {
            dp[i][i + 1] = true;
            countOfPalindromes += 1;
        }
    }

    for (let length = 3; length <= n; length++) {
        for (let i = 0; i <= n - length; i++) {
            const j = i + length - 1;
            if (s[i] === s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                countOfPalindromes += 1;
            }
        }
    }

    return countOfPalindromes;
};

Go Code

func countSubstrings(s string) int {
	n := len(s)
	if n == 1 {
		return 1
	}

	dp := make([][]bool, n)
	for i := range dp {
		dp[i] = make([]bool, n)
	}
	countOfPalindromes := 0

	// one length
	for i := 0; i < n; i++ {
		dp[i][i] = true
		countOfPalindromes++
	}

	// two length
	for i := 0; i < n-1; i++ {
		if s[i] == s[i+1] {
			dp[i][i+1] = true
			countOfPalindromes++
		}
	}

	for length := 3; length <= n; length++ {
		for i := 0; i <= n-length; i++ {
			j := i + length - 1
			if s[i] == s[j] && dp[i+1][j-1] {
				dp[i][j] = true
				countOfPalindromes++
			}
		}
	}

	return countOfPalindromes
}

Complexity Analysis

Time Complexity: O(N²)
Space Complexity: O(N²)