Leetcode 647. Palindromic Substrings

Problem

Given a string s, determine how many contiguous substrings within it are palindromes. A palindrome is a sequence that reads the same forwards and backwards.

Every single character is considered a palindrome. You need to count all possible palindromic substrings, including overlapping ones.

Requirements

1. Count all contiguous substrings that are palindromes
2. Include single-character substrings (each counts as a palindrome)
3. Return the total count as an integer
4. Handle both odd-length and even-length palindromes

Constraints

• 1 ≤ length of s ≤ 1000
• s consists of lowercase English letters only
• Expected time complexity: O(n²) or better
• Expected space complexity: O(1) auxiliary space (excluding input)

Examples

Example 1:

Input: s = "abc" Output: 3 Explanation: The three palindromic substrings are: "a", "b", "c"

Example 2:

Input: s = "aaa" Output: 6 Explanation: Six palindromic substrings are: "a" (three times), "aa" (twice), "aaa" (once)

Example 3:

Input: s = "racecar" Output: 10 Explanation: All 7 single characters are palindromes. Additionally: "cec", "aceca", and "racecar"

Hint 1: Expand Around Center Consider each possible center position in the string. A palindrome can have its center at a single character (odd-length palindromes) or between two characters (even-length palindromes). Try expanding outward from each potential center while characters match.

Hint 2: Two Types of Centers For a string of length n, there are (2n - 1) possible centers: n centers at each character position for odd-length palindromes, and (n - 1) centers between adjacent characters for even-length palindromes. Count palindromes by expanding from each center.

Hint 3: Optimization You don't need to store all palindromes or check every substring. Just expand from each center and count valid palindromes as you expand. Stop expanding when characters no longer match.

Full Solution `` Approach Explanation:

The solution uses the "expand around center" technique:

1. Center Identification: For each position in the string, we consider it as a potential palindrome center. There are two types:

   • Odd-length palindromes: center is at index i (expand from i, i)
   • Even-length palindromes: center is between i and i+1 (expand from i, i+1)

2. Expansion: From each center, we expand outward while characters match. Each successful expansion represents a valid palindrome.

3. Counting: Every time we find matching characters during expansion, we increment our count.

Time Complexity: O(n²) where n is the length of the string. We have O(n) centers, and each expansion can take O(n) time in the worst case (e.g., a string of all same characters).

Space Complexity: O(1) auxiliary space. We only use a constant amount of extra space for counters and pointers.

Alternative Approach: Manacher's algorithm can solve this in O(n) time, but it's more complex to implement and the O(n²) solution is typically sufficient for interview settings with strings up to length 1000.