Palindromic Substrings
Palindromic Substrings is a medium dynamic programming problem solved with the strings pattern.
The best approach, optimal (expand around center), runs in O(n²) time and O(1) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force up.
Problem
Given a string s, count how many of its substrings are palindromes. A substring is a contiguous, non-empty run of characters, and a palindrome reads the same from left to right as from right to left.
Substrings are counted by position, not by content: two equal substrings that start or end at different indices are counted separately.
Examples
Example 1
- Input
s = "aba"- Output
4- Why
- The palindromes are "a", "b", "a" and "aba".
Example 2
- Input
s = "zzz"- Output
6- Why
- Three "z", two "zz" (at different positions) and one "zzz".
Example 3
- Input
s = "abc"- Output
3- Why
- Only the single letters read the same both ways.
Constraints
1 <= s.length <= 1000scontains only lowercase English letters.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n³) | O(1) |
| Better (interval DP table) | O(n²) | O(n²) |
| Optimal (expand around center) | O(n²) | O(1) |
1Brute force
O(n³)There are about n²/2 substrings and each check can take O(n).O(1)Only a few indices; no substring is copied.Generate every substring by its start and end index and check each one with two pointers moving inward.
- For every start i and every end j >= i, check whether s[i..j] is a palindrome.
- The check walks l = i and r = j toward each other and fails on the first mismatch.
- Count the substrings that pass.
class Solution {
public int countSubstrings(String s) {
int n = s.length(), count = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if (isPal(s, i, j)) count++;
}
}
return count;
}
private boolean isPal(String s, int l, int r) {
while (l < r) {
if (s.charAt(l) != s.charAt(r)) return false;
l++;
r--;
}
return true;
}
}class Solution:
def countSubstrings(self, s: str) -> int:
n = len(s)
count = 0
for i in range(n):
for j in range(i, n):
if self.isPal(s, i, j):
count += 1
return count
def isPal(self, s: str, l: int, r: int) -> bool:
while l < r:
if s[l] != s[r]:
return False
l += 1
r -= 1
return Trueclass Solution {
public:
int countSubstrings(string s) {
int n = s.size(), count = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if (isPal(s, i, j)) count++;
}
}
return count;
}
private:
bool isPal(const string& s, int l, int r) {
while (l < r) {
if (s[l] != s[r]) return false;
l++;
r--;
}
return true;
}
};function countSubstrings(s) {
const n = s.length;
let count = 0;
const isPal = (l, r) => {
while (l < r) {
if (s[l] !== s[r]) return false;
l++;
r--;
}
return true;
};
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
if (isPal(i, j)) count++;
}
}
return count;
}2Better (interval DP table)
O(n²)Each of the n²/2 cells is filled in O(1).O(n²)The boolean table has n × n cells.Let pal[i][j] say whether s[i..j] is a palindrome. It is true when the end letters match and the inside s[i+1..j-1] is a palindrome (or has length 0 or 1). Fill the table from short substrings to long ones and count the true cells.
- Loop i from n - 1 down to 0 and j from i up to n - 1, so pal[i+1][j-1] is ready before pal[i][j].
- pal[i][j] = s[i] == s[j] && (j - i < 2 || pal[i+1][j-1]).
- Add 1 to the count for every true cell.
class Solution {
public int countSubstrings(String s) {
int n = s.length(), count = 0;
boolean[][] pal = 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 || pal[i + 1][j - 1])) {
pal[i][j] = true;
count++;
}
}
}
return count;
}
}class Solution:
def countSubstrings(self, s: str) -> int:
n = len(s)
count = 0
pal = [[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 pal[i + 1][j - 1]):
pal[i][j] = True
count += 1
return countclass Solution {
public:
int countSubstrings(string s) {
int n = s.size(), count = 0;
vector<vector<bool>> pal(n, vector<bool>(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 || pal[i + 1][j - 1])) {
pal[i][j] = true;
count++;
}
}
}
return count;
}
};function countSubstrings(s) {
const n = s.length;
let count = 0;
const pal = Array.from({ length: n }, () => new 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 || pal[i + 1][j - 1])) {
pal[i][j] = true;
count++;
}
}
}
return count;
}3Optimal (expand around center)
O(n²)2n - 1 centers, and each expansion moves at most n/2 steps.O(1)Only two pointers and a counter.Every palindrome has a center: a letter (odd length) or a gap between two letters (even length). From each of the 2n - 1 centers, expand outward while the two ends match; each successful step is one more palindrome.
- For each index c, expand from (c, c) for odd lengths and from (c, c + 1) for even lengths.
- While l >= 0, r < n and s[l] == s[r]: count one palindrome, then l--, r++.
- Return the total.
class Solution {
public int countSubstrings(String s) {
int count = 0;
for (int c = 0; c < s.length(); c++) {
count += expand(s, c, c);
count += expand(s, c, c + 1);
}
return count;
}
private int expand(String s, int l, int r) {
int found = 0;
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
found++;
l--;
r++;
}
return found;
}
}class Solution:
def countSubstrings(self, s: str) -> int:
count = 0
for c in range(len(s)):
count += self.expand(s, c, c)
count += self.expand(s, c, c + 1)
return count
def expand(self, s: str, l: int, r: int) -> int:
found = 0
while l >= 0 and r < len(s) and s[l] == s[r]:
found += 1
l -= 1
r += 1
return foundclass Solution {
public:
int countSubstrings(string s) {
int count = 0;
for (int c = 0; c < (int)s.size(); c++) {
count += expand(s, c, c);
count += expand(s, c, c + 1);
}
return count;
}
private:
int expand(const string& s, int l, int r) {
int found = 0;
while (l >= 0 && r < (int)s.size() && s[l] == s[r]) {
found++;
l--;
r++;
}
return found;
}
};function countSubstrings(s) {
const expand = (l, r) => {
let found = 0;
while (l >= 0 && r < s.length && s[l] === s[r]) {
found++;
l--;
r++;
}
return found;
};
let count = 0;
for (let c = 0; c < s.length; c++) {
count += expand(c, c);
count += expand(c, c + 1);
}
return count;
}Edge cases to test
- A single character: the answer is 1
- All letters equal: every substring is a palindrome, n(n + 1) / 2 in total
- Even-length palindromes such as "abba", which have no single middle letter
- No repeated letters: only the n single letters count
Hints
Hint 1
Every single letter is a palindrome, so the answer is at least n.
Hint 2
A palindrome stays a palindrome when you strip one letter from each end. Turn that around: grow outward from a middle.
Hint 3
There are 2n - 1 possible middles: n letters (odd lengths) and n - 1 gaps between letters (even lengths).
FAQ
What is the best time complexity for Palindromic Substrings?
Optimal (expand around center) runs in O(n²) time and O(1) extra space. 2n - 1 centers, and each expansion moves at most n/2 steps.
Which pattern does Palindromic Substrings use?
It is a dynamic programming problem that uses the strings pattern. Other problems with the same pattern: Edit Distance, Longest Common Subsequence, Longest Palindromic Subsequence.
Is there a brute force solution for Palindromic Substrings?
Yes. Brute force takes O(n³) time and O(1) space. Generate every substring by its start and end index and check each one with two pointers moving inward.
Which edge cases should I test for Palindromic Substrings?
A single character: the answer is 1; All letters equal: every substring is a palindrome, n(n + 1) / 2 in total; Even-length palindromes such as "abba", which have no single middle letter; No repeated letters: only the n single letters count.