Palindromic Substrings

Palindromic Substrings

What is this problem about?

The Palindromic Substrings problem asks you to count the total number of palindromic substrings in a string. Every single character is a palindrome, and longer palindromes are found by expanding from centers. This Palindromic Substrings coding problem uses the expand-around-center technique or Manacher's algorithm for O(n) time.

Why is this asked in interviews?

Apple, Goldman Sachs, Microsoft, Meta, Amazon, Google, Bloomberg, and dozens more ask this because it tests the expand-around-center palindrome technique — a fundamental string algorithm pattern. The two pointers, string, and dynamic programming interview pattern is directly demonstrated.

Algorithmic pattern used

Expand around each center. For each possible center (single characters for odd-length palindromes, pairs for even-length), expand outward while characters match. Each valid expansion contributes 1 palindromic substring. Total centers: 2n-1. Total time: O(n²).

Manacher's O(n): Precomputes the max palindrome radius at each center in linear time.

Example explanation

s="abc". Centers: a(1),ab(0),b(1),bc(0),c(1). Total = 1+0+1+0+1 = 3 (just individual characters).

s="aaa". Centers: a(1),aa(1),a(1 each from pos),aaa center...

• Center 'a'@0: "a"→count=1.
• Center 'aa'@0-1: "aa"→count=1.
• Center 'a'@1: "a","aaa"→count=2.
• Center 'aa'@1-2: "aa"→count=1.
• Center 'a'@2: "a"→count=1. Total = 1+1+2+1+1 = 6 palindromes.

Common mistakes candidates make

• Counting substrings instead of palindromic substrings.
• Not expanding from both odd and even centers.
• Using O(n²) DP when expand-around-center is equally O(n²) but simpler.
• Off-by-one: 2n-1 total centers (n odd, n-1 even).

Interview preparation tip

Palindromic Substrings and Longest Palindromic Substring both use the expand-around-center technique. Master this technique first (very clean implementation), then learn Manacher's O(n) algorithm as an optimization to mention. For counting, incrementally add 1 per successful expansion. Practice both approaches until the expand-around-center loop feels automatic.