Palindromic Substrings - Solution & Explanation
Problem Statement
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.
The C solution uses two nested loops. The outer loop iterates over possible centers of palindromic substrings, which are twice the length of the string minus one (to account for centers in between characters for even-length palindromes). The inner loop expands from the center until a non-palindromic string is found.
Complexity
Time complexity: O(n^2), where n is the length of the string.
Space complexity: O(1), since we're only using a few auxiliary variables.
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.
This C solution fills a DP table where dp[i][j] is true if the substring s[i..j] is a palindrome, using known results of smaller substrings to build the solution for larger substrings.
Complexity
Time complexity: O(n^2), Space complexity: O(n^2), due to the storage of the DP table.
Approach 3: 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.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Expand Around Center | Time complexity: O(n^2), where n is the length of the string. |
| Dynamic Programming | Time complexity: O(n^2), Space complexity: O(n^2), due to the storage of the DP table. |
| Manacher's Algorithm | — |
Detailed 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 |
Video Solution
Palindromic Substrings - Leetcode 647 - Python • NeetCode • 226,143 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Palindromic Substrings easy or hard?
How to solve Palindromic Substrings in O(n)?
What is the best approach for Palindromic Substrings?
Is Palindromic Substrings asked at Google/Amazon/Meta?
What data structure is used in Palindromic Substrings?
What is the time complexity of Palindromic Substrings?
Palindromic Substrings Python or Java solution approach
Ready to solve this problem?
Practice Palindromic Substrings with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor