How do you approach Palindromic Substrings?

Every single character is a palindrome.

What is the time complexity of Palindromic Substrings?

Time complexity: O(n^2). Space complexity: O(1).

What are common mistakes on Palindromic Substrings?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

Sitelet https://gitgood.dev/coding/palindromic-substrings

gitGood.dev

← Back to problems

Palindromic Substrings

MediumAlgorithms

Description

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 substrings: "a", "b", "c".

Example 2

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.

Palindromic Substrings: approach, complexity and pitfalls

A medium dynamic programming problem, graded against 7 test cases (4 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

If you are stuck

Show the 3-step hint ladder

Every single character is a palindrome.
Expand around each possible center - there are 2n-1 centers (n single chars + n-1 gaps).
For each center, expand outward while characters match.

The optimal approach

Show the approach: Expand Around Center

For each possible center (single character or between two characters), expand outward while the substring remains a palindrome. Count each valid expansion.

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

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.