Approach Summary
Expand around each center (n odd-length centers + n-1 even-length centers). Count each valid expansion.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Expand Around Center (Optimal) | O(n^2) | O(1) | Expand outward from 2n - 1 centers, incrementing total whenever characters match. |
| 2 Approach 2: 2D Dynamic Programming Table | O(n²) | O(n²) | Builds an n x n boolean table where dp[i][j] indicates whether substring s[i...j] is a palindrome. |
Step 1: Baseline
Approach 1: Expand Around Center (Optimal)
Time: O(n^2)
Space: O(1)
Every palindromic substring is centered around an index i (for odd lengths like "aba") or between i and i + 1 (for even lengths like "abba"). A helper function expands outwards from a center while characters match, incrementing the count for each valid palindrome found.
Approach 1: Expand Around Center (Optimal) Implementation
Approach 1: Expand Around Center (Optimal)
class Solution {
public int expandAroundCenter(String s, int left, int right) {
int count = 0;
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
count++;
left--;
right++;
}
return count;
}
public int countSubstrings(String s) {
int count = 0;
int n = s.length();
for (int i = 0; i < n; i++) {
count += expandAroundCenter(s, i, i);
count += expandAroundCenter(s, i, i + 1);
}
return count;
}
}class Solution {
public:
int expandAroundCenter(string& s, int left, int right) {
int count = 0;
while (left >= 0 && right < s.size() && s[left] == s[right]) {
count++;
left--;
right++;
}
return count;
}
int countSubstrings(string s) {
int n = s.size();
int count = 0;
for (int i = 0; i < n; i++) {
count += expandAroundCenter(s, i, i);
count += expandAroundCenter(s, i, i + 1);
}
return count;
}
};class Solution:
def countSubstrings(self, s: str) -> int:
def expand(left, right):
cnt = 0
while left >= 0 and right < len(s) and s[left] == s[right]:
cnt += 1
left -= 1
right += 1
return cnt
return sum(expand(i, i) + expand(i, i + 1) for i in range(len(s)))function countSubstrings(s) {
function expand(left, right) {
let cnt = 0;
while (left >= 0 && right < s.length && s[left] === s[right]) {
cnt++; left--; right++;
}
return cnt;
}
let total = 0;
for (let i = 0; i < s.length; i++) {
total += expand(i, i) + expand(i, i + 1);
}
return total;
} Step 2: Most Optimized
Approach 2: 2D Dynamic Programming Table
Time: O(n²)
Space: O(n²)
Define dp[i][j] = true if s[i..j] is a palindrome. Base cases: single characters dp[i][i] = true; two characters dp[i][i+1] = (s[i] == s[i+1]). For length >= 3, dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]. Count total true entries.
Approach 2: 2D Dynamic Programming Table Implementation
Approach 2: 2D Dynamic Programming Table
class Solution {
public int countSubstrings(String s) {
int n = s.length(), count = 0;
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;
count++;
}
}
}
return count;
}
}class Solution {
public:
int countSubstrings(string s) {
int n = s.size(), count = 0;
vector<vector<bool>> dp(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 || dp[i + 1][j - 1])) {
dp[i][j] = true;
count++;
}
}
}
return count;
}
};class Solution:
def countSubstrings(self, s: str) -> int:
n = len(s)
dp = [[False] * n for _ in range(n)]
count = 0
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
count += 1
return countfunction countSubstrings(s) {
const n = s.length;
const dp = Array.from({length: n}, () => new Array(n).fill(false));
let count = 0;
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;
count++;
}
}
}
return count;
}Edge Cases to Watch
- Single character string (e.g. "a"; exactly 1 palindrome)
- All characters identical (e.g. "aaa"; total n*(n+1)/2 = 6 palindromes: 3 length-1, 2 length-2, 1 length-3)
- All unique characters (e.g. "abc"; exactly 3 palindromes of length 1)
Algorithmic Pattern
View Pattern Guide →
Master the Dynamic Programming Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Dynamic Programming pattern.
Framework: Dynamic Programming • Interview Prep: Tested at FAANG •
Explore all Dynamic Programming problems & invariants →
How to Recognize This Pattern
- Count palindromic substrings, not just longest
- Expand-around-center: O(n²) time, O(1) space
Complexity Analysis
Time Complexity
O(n²)
Space Complexity
O(1)
Tags
String Dynamic Programming
Frequently Asked Questions
What is the optimal time and space complexity for Palindromic Substrings?
The optimal solution for Palindromic Substrings achieves O(n²) runtime complexity and requires O(1) auxiliary space. Time complexity is O(n^2) because each center expands at most O(n) steps. Space complexity is O(1) auxiliary space as only an integer counter is stored.
How do I identify that Palindromic Substrings requires the Dynamic Programming pattern?
In technical interviews, look for key problem signals: Count palindromic substrings, not just longest; Expand-around-center: O(n²) time, O(1) space. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Dynamic Programming strategy.
What critical edge cases must be handled in Palindromic Substrings?
Essential edge cases to verify include: Single character string (e.g. "a"; exactly 1 palindrome); All characters identical (e.g. "aaa"; total n*(n+1)/2 = 6 palindromes: 3 length-1, 2 length-2, 1 length-3); All unique characters (e.g. "abc"; exactly 3 palindromes of length 1). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Palindromic Substrings?
Palindromic Substrings is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Facebook, Amazon, Bloomberg.