Skip to main content

647. Palindromic Substrings

medium

Count how many palindromic substrings s contains. Same 2D table as Longest Palindromic Substring, but you sum trues instead of tracking the max span.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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.

Constraints

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

Examples

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".

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Expand-around-center: every index is the center of some odd-length and some even-length window. Count expansions until the window stops matching.

Hint 2

DP version: dp[i][j] = true iff s[i..j] is a palindrome. Add up the trues.

Hint 3

Both run in O(n^2). The expand-around-center version is O(1) extra space.

Solution approach

Reveal approach

Two parallel approaches. Expand-around-center: for each index i from 0 to n-1, run two expansions — one with the center at (i, i) (odd-length palindromes) and one with the center at (i, i+1) (even-length). Each expansion increments the answer while s[left] == s[right], then steps left-- and right++ until the window breaks. DP version: build a 2D boolean table where dp[i][j] = true iff s[i..j] is a palindrome (s[i] == s[j] AND (j - i < 2 OR dp[i+1][j-1])). Sum the trues. Both are O(n^2) time; expand-around-center is O(1) space.

Complexity

Time
O(n^2)
Space
O(1)

Related patterns

  • dynamic-programming
  • two-pointers
  • string-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Palindromic Substrings and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →