Solution: Count of Palindromic Substrings

Grokking the Coding Interview: Patterns for Coding Questions

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Count of Palindromic Substrings

Table of Contents

Contents are not accessible

Problem Statement

Given a string, find the total number of palindromic substrings in it. Please note we need to find the total number of substrings and not subsequences.

Example 1:

Input: "abdbca"
Output: 7
Explanation: Here are the palindromic substrings, "a", "b", "d", "b", "c", "a", "bdb".

Example 2:

Input: = "cddpd"
Output: 7
Explanation: Here are the palindromic substrings, "c", "d", "d", "p", "d", "dd", "dpd".

Example 3:

Input: = "pqr"
Output: 3
Explanation: Here are the palindromic substrings,"p", "q", "r".

Constraints:

1 <= st.length <= 1000
st consists only of lowercase English letters.

Solution

This problem follows the "Longest Palindromic Subsequence" pattern, and can be easily converted to "Longest Palindromic Substring". The only difference is that instead of calculating the longest palindromic substring, we will instead count all the palindromic substrings.

Let's jump directly to the bottom-up dynamic programming solution:

Python3

. . . .

The time and space complexity of the above algorithm is $O(n^2)$ , where 'n' is the length of the input string.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible