Palindromic Substrings

• Difficulty: Medium
• Topics: Two Pointers, String, Dynamic Programming
• Link: https://leetcode.com/problems/palindromic-substrings/

Problem Description

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.

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".

Constraints:

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

Solution

1. Problem Deconstruction

Technical Restatement:
Given a string s of length n, count all contiguous substrings s[i:j] (for 0 ≤ i ≤ j < n) where the substring equals its reverse. A palindrome satisfies s[k] = s[i+j-k] for all k ∈ [i, j].

Beginner Explanation:
Find every possible contiguous segment of the string that reads the same forwards and backwards. For example, in “aba”, segments are “a”, “b”, “a”, and “aba”.

Mathematical Formulation:
Define the indicator function:

$$\mathbf{1}_P(i,j) = \begin{cases} 1 & \text{if } s[i:j+1] \text{ is a palindrome} \\ 0 & \text{otherwise} \end{cases}$$

The solution computes:

$$\sum_{i=0}^{n-1} \sum_{j=i}^{n-1} \mathbf{1}_P(i,j)$$

Constraint Analysis:

• 1 ≤ s.length ≤ 1000:
  • Allows O(n²) solutions (max 1e6 operations), but O(n³) is infeasible (1e9 ops).
  • Edge: Single-character strings (min length) yield n palindromes.
• Lowercase English letters:
  • No case sensitivity or special characters; simplifies equality checks.
• Hidden Edge Cases:
  • Uniform strings (e.g., “aaa”) maximize palindromic substrings (n(n+1)/2).
  • Entire string as palindrome requires counting nested palindromes (e.g., “racecar”).

---

2. Intuition Scaffolding

Analogies:

1. Real-World (Domino Effect):
   Stand at a domino (character); check if adjacent dominoes match symmetrically outward. Each match forms a palindrome.
2. Gaming (Mirror Portal):
   In a side-scroller, your character is a “mirror portal”. Entities passing through reflect identically outward until asymmetry breaks the portal.
3. Mathematical (Symmetric Radial Expansion):
   Model centers as points c ∈ [0, 2n-1]. For each center, expand radially while symmetry holds, counting valid intervals.

Common Pitfalls:

1. Ignoring Even-Length Palindromes: Only checking odd-length (“aba”) misses “aa”.
2. Brute-Force Reversal Check: O(n³) by reversing each substring → timeout for n=1000.
3. Overcounting/Undercounting: Failing to handle overlapping palindromes (e.g., “aaa” has 6, not 3).
4. DP Base Case Errors: Forgetting single/double-character bases in dynamic programming.
5. Center Index Miscalculation: Incorrectly mapping centers to indices in expansion.

---

3. Approach Encyclopedia

Approach 1: Brute Force (O(n³))
Pseudocode:

def countSubstrings(s):  
    n = len(s)  
    count = 0  
    for i in range(n):            # Start index  
        for j in range(i, n):     # End index  
            substr = s[i:j+1]  
            if substr == substr[::-1]:  # Check palindrome  
                count += 1  
    return count  

Complexity Proof:

• Time: Σᵢ₌₀ⁿ⁻¹ Σⱼ₌ᵢⁿ⁻¹ (j - i + 1) = Σᵢ₌₀ⁿ⁻¹ [ (n-i)(n-i+1)/2 ] → O(n³).
• Space: O(1) (no extra storage).

Visualization:

s = "abc"  
Substrings:  
  "a" → ✓, "b" → ✓, "c" → ✓  
  "ab" → ✗, "bc" → ✗  
  "abc" → ✗  
Total = 3  

Approach 2: Dynamic Programming (O(n²) Time, O(n²) Space)
Pseudocode:

def countSubstrings(s):  
    n = len(s)  
    dp = [[False] * n for _ in range(n)]  
    count = 0  
    # Base case 1: length=1  
    for i in range(n):  
        dp[i][i] = True  
        count += 1  
    # Base case 2: length=2  
    for i in range(n-1):  
        if s[i] == s[i+1]:  
            dp[i][i+1] = True  
            count += 1  
    # Length ≥ 3  
    for length in range(3, n+1):  
        for i in range(n-length+1):  
            j = i + length - 1  
            if s[i] == s[j] and dp[i+1][j-1]:  
                dp[i][j] = True  
                count += 1  
    return count  

Complexity Proof:

• Time: O(n²) (filling n²/2 DP entries).
• Space: O(n²) (DP table size).

Visualization (s=“aba”):

DP Table:  
  i\j | 0    1    2  
  ------------------  
  0   | T    F    T   ✓ "a", ✗ "ab", ✓ "aba"  
  1   |      T    F   ✓ "b", ✗ "ba"  
  2   |           T   ✓ "a"  
Count = 4  

Approach 3: Expand Around Centers (O(n²) Time, O(1) Space)
Pseudocode:

def countSubstrings(s):  
    n = len(s)  
    count = 0  
    for i in range(n):  
        # Odd-length: center at i  
        l, r = i, i  
        while l >= 0 and r < n and s[l] == s[r]:  
            count += 1  
            l -= 1  # Expand left  
            r += 1  # Expand right  
        # Even-length: center between i and i+1  
        l, r = i, i+1  
        while l >= 0 and r < n and s[l] == s[r]:  
            count += 1  
            l -= 1  
            r += 1  
    return count  

Complexity Proof:

• Time: O(n²) — 2n-1 centers, each expands ≤ n/2 steps. Worst-case (uniform string) has n(n+1)/2 palindromes → O(n²).
• Space: O(1) (constant pointers).

Visualization (s=“aaa”):

Center i=0 (odd):  
  [0,0] → "a" ✓ → expand: [-1,1] ✗ → count=1  
Center i=0 (even):  
  [0,1] → "aa" ✓ → expand: [-1,2] ✗ → count=2  
Center i=1 (odd):  
  [1,1] → "a" ✓ → expand: [0,2] → "aaa" ✓ → [-1,3] ✗ → count=4  
Center i=1 (even):  
  [1,2] → "aa" ✓ → [0,3] ✗ → count=5  
Center i=2 (odd):  
  [2,2] → "a" ✓ → count=6  

---

4. Code Deep Dive

Optimal Solution (Expand Around Centers):

def countSubstrings(s: str) -> int:  
    n = len(s)  
    ans = 0  # Tracks total palindromic substrings  
    for i in range(n):  # Traverse each center  
        # Odd-length: center at s[i]  
        l, r = i, i  
        while l >= 0 and r < n and s[l] == s[r]:  
            ans += 1  # Valid palindrome found  
            l -= 1    # Expand left toward start  
            r += 1    # Expand right toward end  
        # Even-length: center between s[i] and s[i+1]  
        l, r = i, i+1  
        while l >= 0 and r < n and s[l] == s[r]:  
            ans += 1  
            l -= 1  
            r += 1  
    return ans  

Line-by-Line Annotation:

1. n = len(s): Store string length.
2. ans = 0: Initialize palindrome counter.
3. for i in range(n): Iterate each character as a center.
4. l, r = i, i: Set pointers for odd-length center.
5. while l >= 0 ...:
   • Check bounds and character equality.
   • ans += 1: Count valid palindrome.
   • l -= 1; r += 1: Expand symmetrically.
6. l, r = i, i+1: Set pointers for even-length center.
7. while ...: Same expansion for even-length.

Edge Case Handling:

• Single Character (s="a"):
  • Odd-center at i=0: Counts “a” → ans=1.
  • Even-center: r=1 out-of-bounds → skipped.
• Uniform String (s="aaa"):
  • Centers at i=1 (odd) finds “a”, “aaa”.
  • Centers at i=0 (even) finds “aa”.
• No Palindromes (s="abc"):
  • Even-centers skip all (e.g., s[0]!=s[1]).

---

5. Complexity War Room

Hardware-Aware Analysis:

• For n=1000, worst-case ~500k operations (palindromes in uniform string).
• Memory: O(1) → ~200 bytes (fits in CPU cache).

Industry Comparison Table:

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(n³)	O(1)	10/10	❌ (Fails n=1000)
Dynamic Programming	O(n²)	O(n²)	8/10	✅ (Correct)
Expand Centers	O(n²)	O(1)	9/10	✅✅ (Optimal)
Manacher	O(n)	O(n)	5/10	⚠ (Overkill)

---

6. Pro Mode Extras

Variants:

1. List All Palindromic Substrings:
   Modify “Expand Centers” to record (l, r) indices instead of counting.
2. Longest Palindromic Substring (LC 5):
   Track max_len and start during expansion.
3. Palindromic Subsequences (LC 516):
   Use DP: dp[i][j] = max(dp[i+1][j], dp[i][j-1], (dp[i+1][j-1] + 2) if s[i]==s[j]).
4. Multi-Transaction Palindromes (Hypothetical):
   Count palindromic substrings with ≤ k partitions (unrelated to this problem).

Interview Cheat Sheet:

• First Mention: Time/space complexity.
• Key Insight: Palindromes mirror around a center.
• Corner Cases: Single char, uniform strings.
• Trap Question: “Can we do better than O(n²)?” → Manacher’s (O(n)) is complex and rarely expected.