Palindromic Substrings

medium

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.

Test Cases

Copy an input into the main harness and Run to verify

Input

s = "abc"

Expected Output

3

Explanation: Three palindromic strings: "a", "b", "c".

Input

s = "aaa"

Expected Output

6

Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Hint 1 — click to reveal

Every palindrome has a centre — either a character, or the gap between two characters.

Hint 2 — click to reveal

There are 2n - 1 possible centres. Expand outward from each.

Java Compiler