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.

#647

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

回文子串

给你一个字符串 s ，请你统计并返回这个字符串中回文子串的数目。回文字符串是正着读和倒过来读一样的字符串。子字符串是字符串中的由连续字符组成的一个序列。示例 1：输入： s = "abc" 输出： 3 解释：三个回文子串: "a", "b", "c" 示例 2：输入： s = "…

双指针字符串动态规划

题目描述

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

示例 1：

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

1 <= s.length <= 1000
s 由小写英文字母组成

lightbulb

解题思路

方法一：从中心向两侧扩展回文串

我们可以枚举回文串的中心位置，然后向两侧扩展，统计回文串的数量。对于长度为 $n$ 的字符串，回文串的中心位置共有 $2n-1$ 个（包括奇数长度和偶数长度的回文串）。对于每个中心位置，我们向两侧扩展，直到不满足回文串的条件为止，统计回文串的数量。

时间复杂度 $O(n^2)$ ，其中 $n$ 是字符串 $s$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

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

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#1048 最长字符串链 #1147 段式回文 #5 最长回文子串