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
On this page

Problem Statement

Solution

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
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!

On this page

Problem Statement

Solution