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 <= 1000s consists of lowercase English letters.The goal of #647 Palindromic Substrings is to count all substrings in a string that read the same forward and backward. A key observation is that every palindrome expands symmetrically around its center. Using this idea, the most practical solution is the center expansion (two pointers) technique. For each index, treat it as the center of both odd-length and even-length palindromes, then expand outward while characters match. This allows you to discover all valid palindromes efficiently.
Another approach uses Dynamic Programming. Define a DP table where dp[i][j] indicates whether the substring from index i to j is a palindrome. The state depends on matching boundary characters and whether the inner substring is already known to be a palindrome.
The center expansion approach is typically preferred because it achieves O(n²) time with O(1) extra space, while the DP approach requires additional memory for the table.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Center Expansion (Two Pointers) | O(n^2) | O(1) |
| Dynamic Programming | O(n^2) | O(n^2) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
How can we reuse a previously computed palindrome to compute a larger palindrome?
If “aba” is a palindrome, is “xabax” a palindrome? Similarly is “xabay” a palindrome?
Complexity based hint:</br> If we use brute force and check whether for every start and end position a substring is a palindrome we have O(n^2) start - end pairs and O(n) palindromic checks. Can we reduce the time for palindromic checks to O(1) by reusing some previous computation?
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.
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.
1#include <stdio.h>
2#include <string.h>
3
4int countSubstrings(char *s) {
5 int count = 0, n = strlen(s);
6 for (int center = 0; center < 2 * n - 1; ++center) {
7 int left = center / 2;
8 int right = left + center % 2;
9 while (left >= 0 && right < n && s[left] == s[right]) {
10 count++;
11 left--;
12 right++;
13 }
14 }
15 return count;
16}
17
18int main() {
19 char s[] = "aaa";
20 printf("%d\n", countSubstrings(s)); // Output: 6
21 return 0;
22}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.
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.
Time complexity: O(n^2), Space complexity: O(n^2), due to the storage of the DP table.
1#include
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, palindrome-related string problems are common in FAANG-style interviews. Variations like counting palindromes, longest palindromic substring, and palindrome partitioning frequently appear.
The most practical approach is the center expansion method. For each character, expand outward to check both odd and even length palindromes. This method runs in O(n^2) time with only O(1) extra space.
A palindrome mirrors around its center, meaning characters on both sides must match. By expanding two pointers outward from a center, we can efficiently detect every valid palindromic substring.
The problem mainly relies on string traversal and pointer expansion rather than complex data structures. However, a 2D array or matrix can be used in the dynamic programming approach to store palindrome states.
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.