Palindromic Substrings solution and explanation
IBM
Google
9 more videos on this problem
Palindromic Substrings - Leetcode 647 - PythonNeetCode · 15:02 · 226K views
Palindromic Substrings | Blueprint | Palindrome Problems | 4 Approaches | Leetcode 647codestorywithMIK · 57:30 · 22K views
Palindromic Substrings (LeetCode 647) | Full step by step solution with visualsNikhil Lohia · 20:06 · 21K views
Leetcode Visualized: 647. Palindromic SubstringsAlexander Le · 18:07 · 19K views
#Leetcode 647. Palindromic Substrings | Count distinct palindromic substrings in a stringCode with Alisha · 26:11 · 17K views
Leetcode 647. Palindromic Substrings [Java]if else statement · 6:04 · 4K views
Leetcode - Palindromic Substrings (Python)Timothy H Chang · 3:11 · 2K views
Palindromic Substrings - LeetCode 647 - JavaScriptAlgoJS · 6:48 · 2K views
Palindromic Substrings- LeetCode 647 - Python #leetcode #palindromicsubstrings #blind75Deepti Talesra · 9:10 · 1K views
Palindromic Substrings | LeetCode 647 (Medium)Destination FAANG · 13:44 · 1K views
The problem
Given a string s, return the number of palindromic substrings in it.
A string is a palindrome when it reads the same backward as forward.
A substring is a contiguous sequence of characters within the string.
Example 1:
Input: s = "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c".
Example 2:
Input: s = "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
Constraints:
1 <= s.length <= 1000sconsists of lowercase English letters.
Approach overview
Problem Overview: You are given a string s. The task is to count how many substrings of s are palindromes. A substring is valid if it reads the same forward and backward. Single characters count as palindromes, so every index contributes at least one result.
Approach 1: Brute Force Check (O(n^3) time, O(1) space)
The most direct idea is to generate every possible substring and check whether it is a palindrome. Two nested loops choose the start and end indices, producing O(n^2) substrings. For each substring, run a palindrome check using two pointers from both ends toward the center. That check costs O(n) in the worst case, giving an overall complexity of O(n^3). This approach demonstrates the problem definition clearly but becomes too slow for large inputs.
Approach 2: Expand Around Center (O(n^2) time, O(1) space)
A palindrome mirrors around its center. Every palindrome can be expanded from either a single character (odd length) or the gap between two characters (even length). Iterate through the string and treat each index as a potential center. From each center, expand two pointers outward while the characters match. Each successful expansion forms a valid palindromic substring and increments the count. There are 2n - 1 possible centers, and each expansion may scan outward up to O(n), giving O(n^2) time overall with constant extra memory. This technique relies on simple pointer movement and is closely related to Two Pointers and String processing patterns.
Approach 3: Dynamic Programming (O(n^2) time, O(n^2) space)
Dynamic programming stores whether each substring s[i..j] is a palindrome. Define a DP table where dp[i][j] is true if the substring from index i to j is a palindrome. Single characters are always palindromes, and two characters are palindromes if both characters match. For longer substrings, the condition becomes s[i] == s[j] && dp[i+1][j-1]. Iterate over substring lengths from small to large and update the table while counting valid palindromes. The algorithm runs in O(n^2) time but uses O(n^2) memory to store the table. This method is useful for understanding palindrome substructure and practicing Dynamic Programming.
Recommended for interviews: Expand Around Center is the expected solution. It achieves optimal O(n^2) time while using O(1) space and requires only simple pointer logic. Starting with brute force shows you understand the problem, but quickly shifting to center expansion demonstrates strong problem-solving instincts and familiarity with common string patterns.
Approach 1: Expand Around Center
In this approach, consider each character in the string, and each pair of consecutive characters as the center of potential palindromes. From each center, expand outward until the substring is no longer a palindrome. This allows for both odd-length and even-length palindromes to be discovered.
def count_substrings(s: str) -> int:
count, n = 0, len(s)
for center in range(2 * n - 1):
left = center // 2
right = left + center % 2
while left >= 0 and right < n and s[left] == s[right]:
count += 1
left -= 1
right += 1
return count
s = "aaa"
print(count_substrings(s)) # Output: 6public class PalindromeSubstrings {
public static int countSubstrings(String s) {
int count = 0, n = s.length();
for (int center = 0; center < 2 * n - 1; ++center) {
int left = center / 2;
int right = left + center % 2;
while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
count++;
left--;
right++;
}
}
return count;
}
public static void main(String[] args) {
String s = "aaa";
System.out.println(countSubstrings(s)); // Output: 6
}
}#include <iostream>
#include <string>
int countSubstrings(const std::string &s) {
int count = 0, n = s.size();
for (int center = 0; center < 2 * n - 1; ++center) {
int left = center / 2;
int right = left + center % 2;
while (left >= 0 && right < n && s[left] == s[right]) {
++count;
--left;
++right;
}
}
return count;
}
int main() {
std::string s = "aaa";
std::cout << countSubstrings(s) << std::endl; // Output: 6
return 0;
}function countSubstrings(s) {
let count = 0;
const n = s.length;
for (let center = 0; center < 2 * n - 1; ++center) {
let left = Math.floor(center / 2);
let right = left + center % 2;
while (left >= 0 && right < n && s[left] === s[right]) {
count++;
left--;
right++;
}
}
return count;
}
const s = "aaa";
console.log(countSubstrings(s)); // Output: 6#include <stdio.h>
#include <string.h>
int countSubstrings(char *s) {
int count = 0, n = strlen(s);
for (int center = 0; center < 2 * n - 1; ++center) {
int left = center / 2;
int right = left + center % 2;
while (left >= 0 && right < n && s[left] == s[right]) {
count++;
left--;
right++;
}
}
return count;
}
int main() {
char s[] = "aaa";
printf("%d\n", countSubstrings(s)); // Output: 6
return 0;
}using System;
public class PalindromeSubstrings {
public static int CountSubstrings(string s) {
int count = 0, n = s.Length;
for (int center = 0; center < 2 * n - 1; ++center) {
int left = center / 2;
int right = left + center % 2;
while (left >= 0 && right < n && s[left] == s[right]) {
count++;
left--;
right++;
}
}
return count;
}
public static void Main() {
string s = "aaa";
Console.WriteLine(CountSubstrings(s)); // Output: 6
}
}This Python implementation mirrors the previous strategies, expanding around center points in the string to find all palindromic substrings.
Time complexity: O(n^2).
Space complexity: O(1).
Approach 2: Dynamic Programming
Utilizing Dynamic Programming, we can store results of previously calculated palindromic substrings in a table. If we know a substring between two indices is a palindrome, we can extend this information to build larger palindromes, reducing redundant checks.
def count_substrings(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):
dp[i][j] = (s[i] == s[j] and (j - i < 3 or dp[i + 1][j - 1]))
if dp[i][j]:
count += 1
return count
s = "aaa"
print(count_substrings(s)) # Output: 6public class PalindromeSubstrings {
public static int countSubstrings(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int count = 0;
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
dp[i][j] = (s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]));
if (dp[i][j]) count++;
}
}
return count;
}
public static void main(String[] args) {
String s = "aaa";
System.out.println(countSubstrings(s)); // Output: 6
}
}#include <iostream>
#include <vector>
#include <string>
int countSubstrings(const std::string &s) {
int n = s.size();
std::vector<std::vector<bool>> dp(n, std::vector<bool>(n, false));
int count = 0;
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
dp[i][j] = (s[i] == s[j] && (j - i < 3 || dp[i + 1][j - 1]));
if (dp[i][j]) {
count++;
}
}
}
return count;
}
int main() {
std::string s = "aaa";
std::cout << countSubstrings(s) << std::endl; // Output: 6
return 0;
}function countSubstrings(s) {
const n = s.length;
const dp = Array.from({ length: n }, () => 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 < 3 || dp[i + 1][j - 1])) {
dp[i][j] = true;
count++;
}
}
}
return count;
}
const s = "aaa";
console.log(countSubstrings(s)); // Output: 6#include <stdio.h>
#include <stdbool.h>
#include <string.h>
int countSubstrings(char *s) {
int n = strlen(s);
bool dp[n][n];
int count = 0;
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
dp[i][j] = (s[i] == s[j] && (j - i < 3 || dp[i + 1][j - 1]));
if (dp[i][j]) {
count++;
}
}
}
return count;
}
int main() {
char s[] = "aaa";
printf("%d\n", countSubstrings(s)); // Output: 6
return 0;
}using System;
public class PalindromeSubstrings {
public static int CountSubstrings(string s) {
int n = s.Length;
bool[,] dp = new bool[n, n];
int count = 0;
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
dp[i, j] = (s[i] == s[j] && (j - i < 3 || dp[i + 1, j - 1]));
if (dp[i, j]) count++;
}
}
return count;
}
public static void Main() {
string s = "aaa";
Console.WriteLine(CountSubstrings(s)); // Output: 6
}
}This Python solution uses a similar DP table to store whether substrings are palindromes and iteratively build solutions for larger substrings based on these results.
Time complexity: O(n^2), Space complexity: O(n^2).
Approach 3: Expand Around Center
We can enumerate the center position of each palindrome and expand outward to count the number of palindromic substrings. For a string of length n, there are 2n-1 possible center positions (covering both odd-length and even-length palindromes). For each center, we expand outward until the palindrome condition is no longer satisfied, and count the number of palindromic substrings.
The time complexity is O(n^2), where n is the length of string s. The space complexity is O(1).
func countSubstrings(s string) int {
ans, n := 0, len(s)
for k := 0; k < n*2-1; k++ {
i, j := k/2, (k+1)/2
for i >= 0 && j < n && s[i] == s[j] {
ans++
i, j = i-1, j+1
}
}
return ans
}Approach 4: Manacher's Algorithm
In Manacher's algorithm, p[i] - 1 represents the maximum palindrome length centered at position i, and the number of palindromic substrings centered at position i is \left \lceil \frac{p[i]-1}{2} \right \rceil.
The time complexity is O(n) and the space complexity is O(n), where n is the length of string s.
function countSubstrings(s: string): number {
let t = '^#';
for (const c of s) {
t += c + '#';
}
t += '$';
const n = t.length;
const p: number[] = new Array(n).fill(0);
let pos = 0,
maxRight = 0;
let ans = 0;
for (let i = 1; i < n - 1; i++) {
if (maxRight > i) {
p[i] = Math.min(maxRight - i, p[2 * pos - i]);
} else {
p[i] = 1;
}
while (t[i - p[i]] === t[i + p[i]]) {
p[i]++;
}
if (i + p[i] > maxRight) {
maxRight = i + p[i];
pos = i;
}
ans += Math.floor(p[i] / 2);
}
return ans;
}func countSubstrings(s string) int {
t := "^#"
for _, c := range s {
t += string(c)
t += "#"
}
t += "$"
n := len(t)
p := make([]int, n)
pos, maxRight := 0, 0
ans := 0
for i := 1; i < n-1; i++ {
if maxRight > i {
mirror := 2*pos - i
if p[mirror] < maxRight-i {
p[i] = p[mirror]
} else {
p[i] = maxRight - i
}
} else {
p[i] = 1
}
for t[i-p[i]] == t[i+p[i]] {
p[i]++
}
if i+p[i] > maxRight {
maxRight = i + p[i]
pos = i
}
ans += p[i] / 2
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Expand Around Center | Time complexity: O(n^2). |
| Dynamic Programming | Time complexity: O(n^2), Space complexity: O(n^2). |
| Expand Around Center | – |
| Manacher's Algorithm | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Palindrome Check | O(n^3) | O(1) | Conceptual baseline or when learning substring enumeration |
| Expand Around Center | O(n^2) | O(1) | Best general solution for interviews and production code |
| Dynamic Programming | O(n^2) | O(n^2) | Useful when you need to reuse palindrome state for related DP problems |
Frequently asked questions
Is Palindromic Substrings easy or hard?
Palindromic Substrings is rated Medium because the brute force idea is straightforward but recognizing the expand-around-center optimization requires pattern recognition. Candidates familiar with palindrome problems usually solve it quickly once they identify the center expansion strategy.
How to solve Palindromic Substrings in O(n)?
An O(n) solution exists using Manacher's Algorithm. It transforms the string and tracks palindrome radii while expanding symmetrically, avoiding repeated comparisons. Although linear time, it is complex and rarely required in interviews compared to the simpler O(n^2) center expansion approach.
What is the best approach for Palindromic Substrings?
The expand-around-center technique is the most practical solution. It treats every index and gap between indices as a potential palindrome center and expands outward while characters match. This approach runs in O(n^2) time with O(1) extra space and is the method most interviewers expect.
Is Palindromic Substrings asked at Google/Amazon/Meta?
Palindromic substring problems frequently appear in technical interviews at companies like Amazon, Google, and Meta because they test string manipulation, two-pointer reasoning, and dynamic programming fundamentals. Variants such as longest palindromic substring or palindrome partitioning are also common.
What data structure is used in Palindromic Substrings?
Most solutions rely on string traversal with two pointers expanding from a center. The dynamic programming approach uses a 2D boolean DP table where dp[i][j] represents whether substring s[i..j] is a palindrome. No advanced data structures are required.
What is the time complexity of Palindromic Substrings?
The optimal common solution runs in O(n^2) time using the expand-around-center technique. Dynamic programming also achieves O(n^2) time but requires O(n^2) space for the DP table. A naive brute force solution takes O(n^3) time because it checks every substring individually.
Palindromic Substrings Python or Java solution approach
In Python or Java, the typical implementation iterates through each index and expands around two centers: one for odd-length palindromes and one for even-length palindromes. Each expansion continues while characters match and increments the count. This results in O(n^2) time and O(1) space.