Palindromic Substrings
Palindromic Substrings
Given a string `s`, find and return the total number of sub strings in `s` that are palindromes.
A palindrome is a string that remains the same when read both forward and backward.
Example 1
Input: s = "abc"
Output: 3
Output: 3
Example 2
Input: s = "aaa"
Output: 6
Output: 6
Constraints:
- 1 <= s.length <= 1000
- “s” consists of lowercase English letters.
Palindromic Substrings Solution
Approaches for solving Palindromic substrings problem
There are mainly 5 approach to solve this problem
- Brute Force Method
- Dynamic Programming Method
- Two Pointers Method
- Two Pointers (Optimal) Method
- Manacher’s algorithms
Approach 1 : Brute Force
- Check every possible substring in the string.
- For each substring, see if it reads the same forward and backward.
- This method is simple but slow because it checks all combinations.
Approach 3 : Two Pointers
- Think of each character (and pair of characters) as the center of a palindrome.
- Expand outward, checking if characters match, and count all palindromes found.
- This method is faster and uses less memory.
Approach 5 : Manacher’s Problem
- Preprocess the string with separators to unify palindrome checks, and maintain an array that tracks the radius of the longest palindrome at each position.
- Use symmetry to skip redundant checks and expand efficiently.
Approach 2 : Dynamic Programming
- Use a table to store if a sub string is a palindrome.
- Start with small sub strings (length 1 and 2), then use this information to check larger ones.
- This saves time by reusing results from smaller sub strings.
Approach 4 : Two Pointers (Optimal)
- Use two pointers to expand around potential centers of palindromes.
- Treat each character and pair of consecutive characters as centers (to handle odd and even-length palindromes).
- Expand outward from each center and count valid palindromic substrings.
1. Brute Force Method:
Check all possible substrings in the string and verify each one to see if it is a palindrome. This method is simple but slow because it explores all combinations.
- Time complexity: O(n^3)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int countSubstrings(string s) {
int res = 0;
for (int i = 0; i < s.size(); i++) {
for (int j = i; j < s.size(); j++) {
int l = i, r = j;
while (l < r && s[l] == s[r]) {
l++;
r--;
}
res += (l >= r);
}
}
return res;
}
};
Java
public class Solution {
public int countSubstrings(String s) {
int res = 0;
for (int i = 0; i < s.length(); i++) {
for (int j = i; j < s.length(); j++) {
int l = i, r = j;
while (l < r && s.charAt(l) == s.charAt(r)) {
l++;
r--;
}
res += (l >= r) ? 1 : 0;
}
}
return res;
}
}
Python
class Solution:
def countSubstrings(self, s: str) -> int:
res = 0
for i in range(len(s)):
for j in range(i, len(s)):
l, r = i, j
while l < r and s[l] == s[r]:
l += 1
r -= 1
res += (l >= r)
return res
JavaScript
class Solution {
/**
* @param {string} s
* @return {number}
*/
countSubstrings(s) {
let res = 0;
for (let i = 0; i < s.length; i++) {
for (let j = i; j < s.length; j++) {
let l = i, r = j;
while (l < r && s[l] === s[r]) {
l++;
r--;
}
res += (l >= r) ? 1 : 0;
}
}
return res;
}
}
2. Dynamic Programming Method
Use a table to track if sub strings are palindromes, starting with smaller ones and building up to larger ones. This approach reuses previous results to avoid redundant checks.
- Time complexity: O(n^2)
- Space complexity: O(n^2)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int countSubstrings(string s) {
int res = 0, n = s.length();
vector> dp(n, vector(n, false));
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (s[i] == s[j] &&
(j - i <= 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
res++;
}
}
}
return res;
}
};
Java
public class Solution {
public int countSubstrings(String s) {
int res = 0, n = s.length();
boolean[][] dp = new boolean[n][n];
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (s.charAt(i) == s.charAt(j) &&
(j - i <= 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
res++;
}
}
}
return res;
}
}
Python
class Solution:
def countSubstrings(self, s: str) -> int:
n, res = len(s), 0
dp = [[False] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i, n):
if s[i] == s[j] and (j - i <= 2 or dp[i + 1][j - 1]):
dp[i][j] = True
res += 1
return res
JavaScript
class Solution {
/**
* @param {string} s
* @return {number}
*/
countSubstrings(s) {
let res = 0;
const n = s.length;
const dp = Array.from({ length: n }, () => Array(n).fill(false));
for (let i = n - 1; i >= 0; i--) {
for (let j = i; j < n; j++) {
if (s[i] === s[j] &&
(j - i <= 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
res++;
}
}
}
return res;
}
}
3. Two Pointers Method
Expand around each character (or pair of characters) as the center of a potential palindrome. Count all valid palindromes found by comparing characters outward.
- Time complexity: O(n^2)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int countSubstrings(string s) {
int res = 0;
for (int i = 0; i < s.size(); i++) {
int l = i, r = i;
while (l >= 0 && r < s.size() &&
s[l] == s[r]) {
res++;
l--;
r++;
}
l = i;
r = i + 1;
while (l >= 0 && r < s.size() &&
s[l] == s[r]) {
res++;
l--;
r++;
}
}
return res;
}
};
Java
public class Solution {
public int countSubstrings(String s) {
int res = 0;
for (int i = 0; i < s.length(); i++) {
int l = i, r = i;
while (l >= 0 && r < s.length() &&
s.charAt(l) == s.charAt(r)) {
res++;
l--;
r++;
}
l = i;
r = i + 1;
while (l >= 0 && r < s.length() &&
s.charAt(l) == s.charAt(r)) {
res++;
l--;
r++;
}
}
return res;
}
}
Python
class Solution:
def countSubstrings(self, s: str) -> int:
res = 0
for i in range(len(s)):
l, r = i, i
while l >= 0 and r < len(s) and s[l] == s[r]:
res += 1
l -= 1
r += 1
l, r = i, i + 1
while l >= 0 and r < len(s) and s[l] == s[r]:
res += 1
l -= 1
r += 1
return res
JavaScript
class Solution {
/**
* @param {string} s
* @return {number}
*/
countSubstrings(s) {
let res = 0;
for (let i = 0; i < s.length; i++) {
let l = i;
let r = i;
while (l >= 0 && r < s.length &&
s.charAt(l) === s.charAt(r)) {
res++;
l--;
r++;
}
l = i;
r = i + 1;
while (l >= 0 && r < s.length &&
s.charAt(l) === s.charAt(r)) {
res++;
l--;
r++;
}
}
return res;
}
}
4. Two Pointers (Optimal) Method
Similar to the regular two-pointer method but optimized to handle odd and even-length palindromes efficiently. It avoids unnecessary checks and uses O(1) space.
- Time complexity: O(n^2)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int countSubstrings(string s) {
int res = 0;
for (int i = 0; i < s.size(); i++) {
res += countPali(s, i, i);
res += countPali(s, i, i + 1);
}
return res;
}
private:
int countPali(string s, int l, int r) {
int res = 0;
while (l >= 0 && r < s.size() && s[l] == s[r]) {
res++;
l--;
r++;
}
return res;
}
};
Java
public class Solution {
public int countSubstrings(String s) {
int res = 0;
for (int i = 0; i < s.length(); i++) {
res += countPali(s, i, i);
res += countPali(s, i, i + 1);
}
return res;
}
private int countPali(String s, int l, int r) {
int res = 0;
while (l >= 0 && r < s.length() &&
s.charAt(l) == s.charAt(r)) {
res++;
l--;
r++;
}
return res;
}
}
Python
class Solution:
def countSubstrings(self, s: str) -> int:
res = 0
for i in range(len(s)):
res += self.countPali(s, i, i)
res += self.countPali(s, i, i + 1)
return res
def countPali(self, s, l, r):
res = 0
while l >= 0 and r < len(s) and s[l] == s[r]:
res += 1
l -= 1
r += 1
return res
JavaScript
class Solution {
/**
* @param {string} s
* @return {number}
*/
countSubstrings(s) {
let res = 0;
for (let i = 0; i < s.length; i++) {
res += this.countPali(s, i, i);
res += this.countPali(s, i, i + 1);
}
return res;
}
/**
* @param {string} s
* @param {number} l
* @param {number} r
* @return {number}
*/
countPali(s, l, r) {
let res = 0;
while (l >= 0 && r < s.length &&
s.charAt(l) === s.charAt(r)) {
res++;
l--;
r++;
}
return res;
}
}
5. Manacher’s Algorithm
This method transforms the string to handle odd and even-length palindromes uniformly by adding separators (e.g., #) between characters. It then uses a center-expansion technique with precomputed symmetry to find all palindromic substrings in O(n) time.
- Time complexity: O(n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
vector<int> manacher(string& s) {
if (!s.size()) return {};
string t = "#" + string(1, s[0]);
for (int i = 1; i < s.size(); ++i)
t += "#" + string(1, s[i]);
t += "#";
int n = t.size();
vector<int> p(n, 0);
int l = 0, r = 0;
for (int i = 0; i < n; i++) {
p[i] = (i < r) ? min(r - i, p[l + (r - i)]) : 0;
while (i + p[i] + 1 < n && i - p[i] - 1 >= 0 &&
t[i + p[i] + 1] == t[i - p[i] - 1])
p[i]++;
if (i + p[i] > r)
l = i - p[i], r = i + p[i];
}
return p;
}
int countSubstrings(string s) {
vector<int> p = manacher(s);
int res = 0;
for (int i : p) {
res += (i + 1) / 2;
}
return res;
}
};
Java
public class Solution {
public int[] manacher(String s) {
StringBuilder t = new StringBuilder("#");
for (char c : s.toCharArray()) {
t.append(c).append("#");
}
int n = t.length();
int[] p = new int[n];
int l = 0, r = 0;
for (int i = 0; i < n; i++) {
p[i] = (i < r) ? Math.min(r - i, p[l + (r - i)]) : 0;
while (i + p[i] + 1 < n && i - p[i] - 1 >= 0 &&
t.charAt(i + p[i] + 1) == t.charAt(i - p[i] - 1)) {
p[i]++;
}
if (i + p[i] > r) {
l = i - p[i];
r = i + p[i];
}
}
return p;
}
public int countSubstrings(String s) {
int res = 0;
int[] p = manacher(s);
for (int i : p) {
res += (i + 1) / 2;
}
return res;
}
}
Python
class Solution:
def countSubstrings(self, s: str) -> int:
def manacher(s):
t = '#' + '#'.join(s) + '#'
n = len(t)
p = [0] * n
l, r = 0, 0
for i in range(n):
p[i] = min(r - i, p[l + (r - i)]) if i < r else 0
while (i + p[i] + 1 < n and i - p[i] - 1 >= 0
and t[i + p[i] + 1] == t[i - p[i] - 1]):
p[i] += 1
if i + p[i] > r:
l, r = i - p[i], i + p[i]
return p
p = manacher(s)
res = 0
for i in p:
res += (i + 1) // 2
return res
JavaScript
class Solution {
/**
* @param {string} s
* @return {number[]}
*/
vector<int> manacher(string& s)
{
const t = '#' + s.split('').join('#') + '#';
const n = t.length;
const p = new Array(n).fill(0);
let l = 0, r = 0;
for (let i = 0; i < n; i++) {
p[i] = (i < r) ? Math.min(r - i, p[l + (r - i)]) : 0;
while (i + p[i] + 1 < n && i - p[i] - 1 >= 0 &&
t[i + p[i] + 1] === t[i - p[i] - 1]) {
p[i]++;
}
if (i + p[i] > r) {
l = i - p[i];
r = i + p[i];
}
}
return p;
}
/**
* @param {string} s
* @return {number}
*/
countSubstrings(s) {
const p = this.manacher(s);
let res = 0;
for (let i of p) {
res += Math.floor((i + 1) / 2);
}
return res;
}
}
