LeetCode 647: Palindromic Substrings (Expand Around Center)
LeetCode 647StringTwo PointersInterviewToday we solve LeetCode 647 - Palindromic Substrings.
Source: https://leetcode.com/problems/palindromic-substrings/
English
Problem Summary
Given a string s, count how many substrings are palindromes. A substring is contiguous, and both single-character and repeated-center cases count.
Key Insight
Every palindrome is defined by a center. For each index, expand for odd length (i,i) and even length (i,i+1) while characters match.
Brute Force and Limitations
Checking every substring then validating palindrome costs O(n^3) in worst case. Dynamic programming can do O(n^2) with extra memory. Center expansion keeps O(n^2) time and O(1) space.
Optimal Algorithm Steps
1) Initialize answer counter to 0.
2) For each index i, expand around (i, i) and add matches.
3) Expand around (i, i + 1) and add matches.
4) During expansion, while left >= 0, right < n, and chars equal: count++, then left--, right++.
Complexity Analysis
Time: O(n^2).
Space: O(1).
Common Pitfalls
- Forgetting even-length centers like "aa".
- Mixing substring count with distinct palindrome count (this problem counts occurrences).
- Off-by-one errors on boundary checks while expanding.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int countSubstrings(String s) {
int n = s.length();
int ans = 0;
for (int i = 0; i < n; i++) {
ans += expand(s, i, i); // odd
ans += expand(s, i, i + 1); // even
}
return ans;
}
private int expand(String s, int left, int right) {
int cnt = 0;
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
cnt++;
left--;
right++;
}
return cnt;
}
}func countSubstrings(s string) int {
n := len(s)
ans := 0
expand := func(left, right int) int {
cnt := 0
for left >= 0 && right < n && s[left] == s[right] {
cnt++
left--
right++
}
return cnt
}
for i := 0; i < n; i++ {
ans += expand(i, i)
ans += expand(i, i+1)
}
return ans
}class Solution {
public:
int countSubstrings(string s) {
int n = (int)s.size();
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += expand(s, i, i);
ans += expand(s, i, i + 1);
}
return ans;
}
private:
int expand(const string& s, int l, int r) {
int cnt = 0;
while (l >= 0 && r < (int)s.size() && s[l] == s[r]) {
++cnt;
--l;
++r;
}
return cnt;
}
};class Solution:
def countSubstrings(self, s: str) -> int:
n = len(s)
def expand(left: int, right: int) -> int:
cnt = 0
while left >= 0 and right < n and s[left] == s[right]:
cnt += 1
left -= 1
right += 1
return cnt
ans = 0
for i in range(n):
ans += expand(i, i)
ans += expand(i, i + 1)
return ansvar countSubstrings = function(s) {
const n = s.length;
function expand(left, right) {
let cnt = 0;
while (left >= 0 && right < n && s[left] === s[right]) {
cnt++;
left--;
right++;
}
return cnt;
}
let ans = 0;
for (let i = 0; i < n; i++) {
ans += expand(i, i);
ans += expand(i, i + 1);
}
return ans;
};中文
题目概述
给定字符串 s，统计其中回文子串的个数。子串要求连续；单字符和多字符回文都计入答案。
核心思路
每个回文都可以由一个“中心”向两侧扩展得到。对每个位置同时尝试奇数中心 (i,i) 和偶数中心 (i,i+1)。
暴力解法与不足
枚举所有子串再逐个判断回文，最坏会到 O(n^3)。DP 可到 O(n^2) 但需要 O(n^2) 空间。中心扩展法保持 O(n^2) 时间且仅 O(1) 额外空间。
最优算法步骤
1）初始化答案计数器为 0。
2）遍历每个下标 i，先从 (i,i) 扩展并累加。
3）再从 (i,i+1) 扩展并累加。
4）扩展时只要边界有效且两端字符相等，就计数并继续向外扩。
复杂度分析
时间复杂度：O(n^2)。
空间复杂度：O(1)。
常见陷阱
- 漏掉偶数长度回文中心（如 "aa"）。
- 把“回文子串个数”误写成“不同回文串个数”。
- 中心扩展的左右边界判断写错导致越界。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int countSubstrings(String s) {
int n = s.length();
int ans = 0;
for (int i = 0; i < n; i++) {
ans += expand(s, i, i); // odd
ans += expand(s, i, i + 1); // even
}
return ans;
}
private int expand(String s, int left, int right) {
int cnt = 0;
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
cnt++;
left--;
right++;
}
return cnt;
}
}func countSubstrings(s string) int {
n := len(s)
ans := 0
expand := func(left, right int) int {
cnt := 0
for left >= 0 && right < n && s[left] == s[right] {
cnt++
left--
right++
}
return cnt
}
for i := 0; i < n; i++ {
ans += expand(i, i)
ans += expand(i, i+1)
}
return ans
}class Solution {
public:
int countSubstrings(string s) {
int n = (int)s.size();
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += expand(s, i, i);
ans += expand(s, i, i + 1);
}
return ans;
}
private:
int expand(const string& s, int l, int r) {
int cnt = 0;
while (l >= 0 && r < (int)s.size() && s[l] == s[r]) {
++cnt;
--l;
++r;
}
return cnt;
}
};class Solution:
def countSubstrings(self, s: str) -> int:
n = len(s)
def expand(left: int, right: int) -> int:
cnt = 0
while left >= 0 and right < n and s[left] == s[right]:
cnt += 1
left -= 1
right += 1
return cnt
ans = 0
for i in range(n):
ans += expand(i, i)
ans += expand(i, i + 1)
return ansvar countSubstrings = function(s) {
const n = s.length;
function expand(left, right) {
let cnt = 0;
while (left >= 0 && right < n && s[left] === s[right]) {
cnt++;
left--;
right++;
}
return cnt;
}
let ans = 0;
for (let i = 0; i < n; i++) {
ans += expand(i, i);
ans += expand(i, i + 1);
}
return ans;
};
Comments