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.

Examples

Example 1:

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Example 3:

Input: s = "racecar"
Output: 10
Explanation: 
Palindromic substrings: "r", "a", "c", "e", "c", "a", "r", "ceec", "aceca", "racecar"

Constraints

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

Thinking Process

  1. Two types of centers: Every palindrome has either a single-character center (odd-length) or a two-character center (even-length)
  • Two indices move toward each other or in the same direction.
  • Works on sorted arrays or when in-place modification is required.
  • Loop invariant: all indices outside [left, right] are already resolved.
Two pointers 1 3 5 7 9 L R move L/R based on comparison

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Opposite ends (this problem) O(n) O(1) Sorted array pair search, reversal
Slow / fast pointers O(n) O(1) Linked list middle, cycle detection
Same-direction chase O(n) O(1) Remove duplicates in-place
Sliding window (variable) O(n) O(1) Subarray with constraint

Solution

Time Complexity: O(n²)
Space Complexity: O(1)

The key insight is that every palindrome expands from a center. For each position in the string, we can have:

  1. Odd-length palindromes: Center at a single character (e.g., “aba” centered at ‘b’)
  2. Even-length palindromes: Center between two characters (e.g., “abba” centered between two ‘b’s)

We iterate through each position and expand outward from both possible centers, counting all palindromic substrings found.

Solution: Expand Around Centers

class Solution {
private:
    int countPalindromesAroundCenter(const string& s, int low, int high) {
        int count = 0;
        while (low >= 0 && high < (int)s.size()) {
            if (s[low] != s[high]) break;
            low--;
            high++;
            count++;
        }
        return count;
    }

public:
    int countSubstrings(string s) {
        int count = 0;
        for (int i = 0; i < (int)s.size(); i++) {
            // Count odd-length palindromes (center at i)
            count += countPalindromesAroundCenter(s, i, i);
            // Count even-length palindromes (center between i and i+1)
            count += countPalindromesAroundCenter(s, i, i + 1);
        }
        return count;
    }
};

Solution Explanation

Approach: Opposite ends (this problem)

Key idea: 1. Two types of centers: Every palindrome has either a single-character center (odd-length) or a two-character center (even-length)

How the code works:

  1. Two types of centers: Every palindrome has either a single-character center (odd-length) or a two-character center (even-length)
    • Two indices move toward each other or in the same direction.
    • Works on sorted arrays or when in-place modification is required.
    • Loop invariant: all indices outside [left, right] are already resolved.

Walkthrough — input s = "abc", expected output 3:

Three palindromic strings: “a”, “b”, “c”.

Time Complexity: O(n²)

  • We iterate through each position: O(n)
  • For each position, we expand outward: O(n) in worst case
  • Total: O(n²)

Space Complexity: O(1)

  • Only using a few variables
  • No extra data structures

    Algorithm Breakdown

Helper Function: countPalindromesAroundCenter

int countPalindromesAroundCenter(const string& s, int low, int high) {
    int count = 0;
    while (low >= 0 && high < (int)s.size()) {
        if (s[low] != s[high]) break;
        low--;
        high++;
        count++;
    }
    return count;
}

How it works:

  1. Start with low and high as the center (or centers for even-length)
  2. Expand outward while characters match
  3. Count each valid palindrome found
  4. Stop when characters don’t match or indices go out of bounds

Why it works:

  • Each expansion creates a new palindromic substring
  • We count all palindromes that can be formed from this center
  • The function handles both odd and even-length palindromes based on initial low and high

Main Function: countSubstrings

int countSubstrings(string s) {
    int count = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        count += countPalindromesAroundCenter(s, i, i);      // Odd-length
        count += countPalindromesAroundCenter(s, i, i + 1); // Even-length
    }
    return count;
}

How it works:

  1. For each position i, check both possible centers
  2. Sum all palindromic substrings found
  3. Return total count

Complexity

Time Complexity: O(n²)

  • We iterate through each position: O(n)
  • For each position, we expand outward: O(n) in worst case
  • Total: O(n²)

Space Complexity: O(1)

  • Only using a few variables
  • No extra data structures

Common Mistakes

  1. Single character: Returns 1 (the character itself is a palindrome)
  2. All same characters: Returns n(n+1)/2 (all substrings are palindromes)

  3. No palindromes longer than 1: Returns n (only single characters are palindromes)

  4. Missing even-length palindromes: Forgetting to check centers between characters
  5. Double counting: Not properly handling boundaries
  6. Index out of bounds: Not checking bounds before accessing array
  7. Wrong expansion logic: Not expanding symmetrically from center

Optimization Tips

  1. Early termination: Can stop early if no more palindromes possible (not applicable here)
  2. Use expand-around-center: More space-efficient than DP
  3. Cache results: Not needed for this problem, but useful for related problems

Pattern Recognition

This problem demonstrates the “Expand Around Centers” pattern:

1. Identify possible centers (single char or between chars)
2. For each center, expand outward symmetrically
3. Count valid expansions

Similar problems:

  • Longest palindromic substring
  • Palindrome partitioning
  • Palindrome-related string problems

Real-World Applications

  1. String Analysis: Finding palindromic patterns in DNA sequences
  2. Text Processing: Detecting palindromic words or phrases
  3. Algorithm Design: Understanding palindrome detection techniques
  4. Interview Preparation: Common pattern in coding interviews

Key Takeaways

  1. Two types of centers: Every palindrome has either a single-character center (odd-length) or a two-character center (even-length)

  2. Expand outward: For each center, expand while characters match

  3. Count incrementally: Each successful expansion creates a new palindromic substring

  4. No overlap: Each center is checked independently, so we count all palindromes exactly once

References

Template Reference