Problem Statement

Given a string, determine the number of palindromic substrings present in it.

A palindromic substring is a sequence of characters that reads the same forwards and backward. The substring can be of any length, including 1.

Example

1. • Input: "racecar"
   • Expected Output: 10
   • Justification: The palindromic substrings are "r", "a", "c", "e", "c", "a", "r", "cec", "aceca", "racecar".
2. • Input: "noon"
   • Expected Output 6
   • Justification: The palindromic substrings are "n", "o", "o", "n", "oo", "noon".
3. • Input: "apple"
   • Expected Output: 6
   • Justification: The palindromic substrings are "a", "p", "p", "l", "e", "pp".

Constraints:

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

Solution

The core idea behind the algorithm is to consider each character in the string as a potential center of a palindrome and then expand outwards from this center to identify all palindromic substrings.

By doing this for every character in the string, we can efficiently count all such substrings. This approach is based on the observation that every palindromic substring has a center (or two centers for even-length palindromes).

1. Initialization: Begin by initializing a counter to zero. This counter will be used to keep track of the number of palindromic substrings.

2. Center Expansion: For each character in the string, treat it as the center of a possible palindrome. There are two scenarios to consider: odd-length palindromes (with a single center) and even-length palindromes (with two centers). For each character, expand outwards and check for both scenarios.

3. Palindrome Check: As you expand outwards from the center, compare the characters. If they are the same, increment the counter. If they are different or if you've reached the boundary of the string, stop expanding.

4. Result: Once all characters have been treated as centers and all possible expansions have been checked, the counter will hold the total number of palindromic substrings.

Algorithm Walkthrough

Let's trace the second example, "noon". Move through the steps one at a time: