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 Sam K., 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

More 2D Dynamic Programming practice problems

See all 2D Dynamic Programming problems →