#647

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Palindromic Substrings

Count all palindromic substrings in a given string using state transition dynamic programming for efficient evaluation.

Problem Statement

Given a string s, return the total number of substrings that read the same forwards and backwards. Palindromes are sequences that mirror around their center.

A substring is any continuous segment of s. You must identify all such palindromic segments, counting duplicates separately, and optimize the search using dynamic programming or center expansion methods.

Examples

Example 1

Input: s = "abc"

Output: 3

Three palindromic strings: "a", "b", "c".

Example 2

Input: s = "aaa"

Output: 6

Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Constraints

1 <= s.length <= 1000
s consists of lowercase English letters.

Solution Approach

Dynamic Programming Table

Create a 2D DP table where dp[i][j] is true if the substring from index i to j is a palindrome. Start with single characters and expand, using dp[i+1][j-1] to determine larger palindromes.

Expand Around Centers

Iterate through each index as a potential center and expand left and right to count palindromes. Consider both odd and even-length centers to cover all cases efficiently.

Combine State Transitions with Two Pointers

Use two pointers to track expansions and update DP results dynamically. Reuse previously computed palindromes to minimize checks, exploiting the state transition property of contiguous palindromes.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity can range from O(n^2) for both DP and center expansion approaches. Space is O(n^2) for DP and O(1) for center expansion. The two-pointer reuse in DP reduces redundant calculations, improving practical performance.

What Interviewers Usually Probe

Look for reuse of smaller palindrome results to count larger ones.
Check handling of odd vs even-length palindromes distinctly.
Expect efficient avoidance of redundant substring checks.

Common Pitfalls or Variants

Common pitfalls

Miscounting even-length vs odd-length palindromes.
Forgetting to initialize single-character substrings as palindromes.
Inefficiently recalculating previously verified palindromes.

Follow-up variants

Return all unique palindromic substrings instead of count.
Find the longest palindromic substring using similar DP strategy.
Count palindromes in a stream of characters with online updates.

FAQ

What is the main approach for Palindromic Substrings problem?

Use dynamic programming with state transitions or expand around centers with two pointers to count all palindromic substrings efficiently.

How do I handle even-length palindromes?

Consider centers between two characters and expand both left and right to detect all even-length palindromic substrings.

What is the optimal space complexity?

Using center expansion requires O(1) extra space, while DP tables use O(n^2). Center expansion is preferred for space efficiency.

Can previously computed palindromes be reused?

Yes, state transitions allow using dp[i+1][j-1] to infer dp[i][j], reducing redundant palindrome checks.

Why is this a state transition dynamic programming problem?

Each palindrome depends on smaller substrings; knowing if a substring is a palindrome lets you determine larger ones through transitions.

terminal

Solution

Solution 1: Expand Around Center

We can enumerate the center position of each palindrome and expand outward to count the number of palindromic substrings. For a string of length $n$, there are $2n-1$ possible center positions (covering both odd-length and even-length palindromes). For each center, we expand outward until the palindrome condition is no longer satisfied, and count the number of palindromic substrings.

1

2

3

4

5

6

7

8

9

class Solution:
    def countSubstrings(self, s: str) -> int:
        ans, n = 0, len(s)
        for k in range(n * 2 - 1):
            i, j = k // 2, (k + 1) // 2
            while ~i and j < n and s[i] == s[j]:
                ans += 1
                i, j = i - 1, j + 1
        return ans

Solution 2: Manacher's Algorithm

In Manacher's algorithm, $p[i] - 1$ represents the maximum palindrome length centered at position $i$, and the number of palindromic substrings centered at position $i$ is $\left \lceil \frac{p[i]-1}{2} \right \rceil$.

1

2

3

4

5

6

7

8

9

class Solution:
    def countSubstrings(self, s: str) -> int:
        ans, n = 0, len(s)
        for k in range(n * 2 - 1):
            i, j = k // 2, (k + 1) // 2
            while ~i and j < n and s[i] == s[j]:
                ans += 1
                i, j = i - 1, j + 1
        return ans

Continue Practicing

#1048 longest string chain #1147 longest chunked palindrome decomposition #5 longest palindromic substring