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.

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