Leetcode 647. Palindromic Substrings

Problem

Leetcode 647 - Palindromic Substrings

Example:

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

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

Approach

Similar to the previous question with Leetcode.5, we can use the same algorithm to solve this but we append it everytime we find a palindrome in res. Once this is done, we can return the len(res).

Here is the Python code for the solution:

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

        n = len(s)
        dp = [[False] * n for _ in range(n)]
        res = []

        for i in range(n):
            dp[i][i] = True
            res.append(s[i])        

        for i in range(n-1):
            if s[i] == s[i+1]:
                dp[i][i+1] = True
                res.append(s[i:i+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
                    res.append(s[i:j+1])
        
        return len(res)    

Time Complexity and Space Complexity

Time Complexity: $O(n^2)$

Space Complexity: $O(n^2)$