Log inSign up
mediumleetcodeNot Started

Palindromic Substrings

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

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 · Example:

Input: s = "abc"
Output: 3
Explanation: Three palindromic substrings: "a", "b", "c".

Example 2 · Example:

Input: s = "aaa"
Output: 6
Explanation: Six palindromic substrings: "a", "a", "a", "aa", "aa", "aaa".

Constraints:

  • 1 <= s.length <= 1000
  • s consists of lowercase English letters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Count palindromic spans using 2N - 1 center expansions.
  • Formulate O(1) space palindrome algorithms.
  • Understand the equivalence between DP boolean tables and center expansions.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Counting the total number of palindromic substrings in a string.
  • Finding all palindromic spans.

Algorithmic Decision Tree:

  • Expand Around Center
  • Manacher's Palindrome Counting
  • 2D DP Palindrome Matrix

Connected Patterns:

Longest Palindromic SubstringPalindrome Partitioning IIShortest Palindrome

1. Brute Force Substring Checking

Intuition

Iterate all start indices i from 0 to n - 1 and all end indices j from i to n - 1. For each substring s[i...j], check if it is a palindrome. If true, increment count.

When to apply: Basic baseline comparison.

Algorithm

  1. Initialize count = 0.
  2. Loop i from 0 to n - 1:
  3. Loop j from i to n - 1:
  4. If isPalindrome(s, i, j): count++.
  5. Return count.

Brute Force Substring Checking

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, a, a]
Current operationSTEP 1 OF 6
Observation: Total substrings in string of length 3 is $N(N+1)/2 = 6$
Visual state
Values and pointers at this exact step
array
S
a
a
a
0
↑ 3 SINGLE CHARS
1
2
Variables at this step
len
1
palindromesFound
3
count
3
Check / comparison
Length 1 substrings: 'a' (idx 0), 'a' (idx 1), 'a' (idx 2).
Decision / next transition
All 3 single characters are palindromes. count = 3.
Why this step matters

Observation: Total substrings in string of length 3 is N(N+1)/2 = 6.

Decision: All 3 single-letter substrings are palindromic. Increment count by 3.

Invariant: Every single character trivially equals its reverse.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5 bool isPalindrome(const std::string& s, int l, int r) {
6 while (l < r) {
7 if (s[l++] != s[r--]) return false;
8 }
9 return true;
10 }
11public:
12 int countSubstrings(std::string s) {
13 int n = s.size(), count = 0;
14 for (int i = 0; i < n; ++i) {
15 for (int j = i; j < n; ++j) {
16 if (isPalindrome(s, i, j)) {
17 count++;
18 }
19 }
20 }
21 return count;
22 }
23};
24
25int main() {
26 Solution sol;
27 std::cout << sol.countSubstrings("abc") << std::endl; // 3
28 std::cout << sol.countSubstrings("aaa") << std::endl; // 6
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(N^3) — N * (N + 1) / 2 substrings, each taking O(N) to check.
  • Space complexity: O(1) extra space

Why Brute Force Doesn't Scale:

Expanding around centers achieves optimal O(N2) time and O(1) space.

Operates purely with integer index pointers with zero auxiliary memory allocations.

2. 2D Dynamic Programming Table

Intuition

Maintain dp[n][n]. A substring s[i...j] is a palindrome if s[i] == s[j] and (j - i < 2 or dp[i+1][j-1] is true). Iterate substring lengths from 1 to N, setting dp[i][j] = true and incrementing total count when valid.

When to apply: When practicing 2D interval DP transitions.

Algorithm

  1. Initialize dp[n][n] = false and count = 0.
  2. Loop len from 1 to n:
  3. Loop i from 0 to n - len:
  4. j = i + len - 1
  5. If s[i] == s[j] and (len <= 2 or dp[i + 1][j - 1]):
  6. dp[i][j] = true
  7. count++
  8. Return count.

2D Dynamic Programming Table

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, a, a]
Current operationSTEP 1 OF 6
Observation: Define boolean table dp[N][N] where dp[i][j] is true if s[i
Visual state
Values and pointers at this exact step
array
S
a
a
a
0
↑ BASE: dp[i][i] = true
1
2
Variables at this step
len
1
baseCount
3
totalCount
3
Check / comparison
Initialize 3x3 table. dp[i][i] = true for all i. count = 3.
Decision / next transition
Length 1 base cases recorded.
Why this step matters

Observation: Define boolean table dp[N][N] where dp[i][j] is true if s[i..j] is a palindrome.

Decision: Set dp[i][i] = true for all single letters. Initialize count = 3.

Invariant: Table diagonal represents length 1 palindromes.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 int countSubstrings(std::string s) {
8 int n = s.size();
9 std::vector<std::vector<bool>> dp(n, std::vector<bool>(n, false));
10 int count = 0;
11
12 for (int len = 1; len <= n; ++len) {
13 for (int i = 0; i <= n - len; ++i) {
14 int j = i + len - 1;
15 if (s[i] == s[j] && (len <= 2 || dp[i + 1][j - 1])) {
16 dp[i][j] = true;
17 count++;
18 }
19 }
20 }
21 return count;
22 }
23};
24
25int main() {
26 Solution sol;
27 std::cout << sol.countSubstrings("abc") << std::endl; // 3
28 std::cout << sol.countSubstrings("aaa") << std::endl; // 6
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(N^2) — Visits all N * (N + 1) / 2 upper-triangular matrix cells.
  • Space complexity: O(N^2)

3. Expand Around Center (O(1) Space)

Intuition

For every index i from 0 to n - 1, expand outward from (i, i) (odd-length palindromes) and (i, i + 1) (even-length palindromes). In the helper countFromCenter(l, r), while l >= 0 and r < n and s[l] == s[r], increment count, decrement l, and increment r. Sum the counts over all centers.

When to apply: The standard gold standard solution for speed and memory efficiency.

Algorithm

  1. Define helper expand(l, r):
  2. c = 0
  3. While l >= 0 && r < n && s[l] == s[r]: c++, l--, r++.
  4. Return c.
  5. Loop i from 0 to n - 1:
  6. total += expand(i, i) + expand(i, i + 1).
  7. Return total.

Dual-Parity Center Expansion Palindrome Tally

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, a, a]
Current operationSTEP 1 OF 6
Observation: Expand odd center at index 0: s[0] = 'a'
Visual state
Values and pointers at this exact step
array
S
a
a
a
0
↑ Center 0: 'a'
1
2
Variables at this step
center
0
oddFound
["a"]
totalCount
1
Why this step matters

Observation: Expand odd center at index 0: s[0] = 'a'.

Decision: Substring "a" is a palindrome. Increment count to 1.

Invariant: Each individual character counts as a single-letter palindrome.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5 int expand(const std::string& s, int l, int r) {
6 int count = 0, n = s.size();
7 while (l >= 0 && r < n && s[l] == s[r]) {
8 count++;
9 l--;
10 r++;
11 }
12 return count;
13 }
14public:
15 int countSubstrings(std::string s) {
16 int total = 0, n = s.size();
17 for (int i = 0; i < n; ++i) {
18 total += expand(s, i, i); // Odd length
19 total += expand(s, i, i + 1); // Even length
20 }
21 return total;
22 }
23};
24
25int main() {
26 Solution sol;
27 std::cout << sol.countSubstrings("abc") << std::endl; // 3
28 std::cout << sol.countSubstrings("aaa") << std::endl; // 6
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(N^2) — Tests 2N - 1 centers with zero extra memory allocation.
  • Space complexity: O(1) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force All SubstringsO(N^3)O(1)Simple nested checks.Very slow, cubic time complexity.
2.2D Dynamic Programming TableO(N^2)O(N^2)Standard table filling.Requires N x N matrix.
3.Expand Around Center (Optimal in Interviews)OptimalO(N^2)O(1) extra spaceZero memory allocation, concise code, highly optimal for N <= 1000.None.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Omitting even-length palindrome centers expand(i, i + 1).

Pitfall 2:

Using string allocation in inner loop causing memory thrashing.

Crucial Edge Cases to Validate:

  • Single character string (s = a): Returns 1 (only s[0] itself).
  • All distinct characters (s = abcdef): Every single character is a palindrome of length 1; returns n = 6.
  • All identical characters (s = aaaa): Returns n * (n + 1) / 2 = 10.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Start by stating that any palindrome expands symmetrically from a center, justifying the 2N - 1 center count.
  2. Implement the O(1) space center expansion directly.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.For a string of all identical characters of length N, what is the exact number of palindromic substrings?

Back to DSA Sheet