Palindromic Substrings - The Three Approaches

Problem: Given a string s, return the number of palindromic substrings in it.

Example: s = "abc" → 3 (substrings: "a", "b", "c")

Example: s = "aaa" → 6 (substrings: "a", "a", "a", "aa", "aa", "aaa")

Understanding the Problem

A palindromic substring is a substring that reads the same forwards and backwards.

We need to count all such substrings (not find the longest, but count ALL of them).

Key difference from Longest Palindromic Substring:

Longest: Find the maximum length palindrome
Count: Count all palindromes

1. Pure Recursion with Expand from Center (O(n²))

The Intuition

Key Insight: Every palindrome has a center. We can expand from each possible center and count palindromes as we find them.

Two types of centers:

Odd length palindromes: Single character center (e.g., "aba")
Even length palindromes: Two character center (e.g., "abba")

public int countSubstrings(String s) {
    if (s == null || s.length() == 0) return 0;

    int count = 0;

    // Try each position as potential center
    for (int i = 0; i < s.length(); i++) {
        // Odd length palindromes (single center)
        count += countPalindromesFromCenter(s, i, i);

        // Even length palindromes (double center)
        count += countPalindromesFromCenter(s, i, i + 1);
    }

    return count;
}

// Expand from center and count all palindromes found
private int countPalindromesFromCenter(String s, int left, int right) {
    int count = 0;

    // Expand while characters match
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        count++;  // Found a palindrome!
        left--;   // Expand left
        right++;  // Expand right
    }

    return count;
}

What Happens with `s = "aaa"`:

Try center at 0 ('a'):
  - Odd:  "a" ✓ (count = 1)
          expand: left=-1, out of bounds
          Total: 1
  - Even: "aa" ✓ (count = 1)
          expand: "aaa" ✓ (count = 2)
          expand: left=-1, out of bounds
          Total: 2

Try center at 1 ('a'):
  - Odd:  "a" ✓ (count = 1)
          expand: "aaa" ✓ (count = 2) [already counted in even from center 0]
          expand: left=-1, out of bounds
          Total: 2
  - Even: "aa" ✓ (count = 1)
          expand: right=4, out of bounds
          Total: 1

Try center at 2 ('a'):
  - Odd:  "a" ✓ (count = 1)
          expand: left=1, right=3, out of bounds
          Total: 1
  - Even: right=4, out of bounds
          Total: 0

Total count: 1 + 2 + 2 + 1 + 1 + 0 = 6 ✓

Wait, let me trace this more carefully:

s = "aaa"

Center at 0:
  Odd (i=0, i=0):  "a" ✓ → count = 1
  Even (i=0, i=1): "aa" ✓ → "aaa" ✓ → count = 2

Center at 1:
  Odd (i=1, i=1):  "a" ✓ → "aaa" ✓ → count = 2
  Even (i=1, i=2): "aa" ✓ → count = 1

Center at 2:
  Odd (i=2, i=2):  "a" ✓ → count = 1
  Even (i=2, i=3): out of bounds → count = 0

Total: 1 + 2 + 2 + 1 + 1 + 0 = 6 ✓

The 6 palindromes are:
1. "a" at index 0
2. "a" at index 1
3. "a" at index 2
4. "aa" at [0,1]
5. "aa" at [1,2]
6. "aaa" at [0,2]

Visualization:

For "aaa":

Expanding from center 0:
  [a] a a     → palindrome "a" (count = 1)

Expanding from centers 0-1:
  [a a] a     → palindrome "aa" (count = 1)
  [a a a]     → palindrome "aaa" (count = 1)

Expanding from center 1:
  a [a] a     → palindrome "a" (count = 1)
  [a a a]     → palindrome "aaa" (already expanded from left)
                 but we count again! (count = 1)

Expanding from centers 1-2:
  a [a a]     → palindrome "aa" (count = 1)

Expanding from center 2:
  a a [a]     → palindrome "a" (count = 1)

Total unique approach counts all expansions = 6

Complexity:

Time: O(n²) - n centers × O(n) expansion per center
Space: O(1) - only storing count

2. Top-Down DP (Memoization - O(n²))

The Intuition

Key Insight: A substring s[i...j] is a palindrome if:

First and last characters match: s[i] == s[j]
Inner substring is also a palindrome: s[i+1...j-1] is palindrome

We recursively check and count all palindromic substrings.

public int countSubstrings(String s) {
    if (s == null || s.length() == 0) return 0;

    int n = s.length();
    Boolean[][] memo = new Boolean[n][n];
    int count = 0;

    // Check all possible substrings
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (isPalindrome(s, i, j, memo)) {
                count++;
            }
        }
    }

    return count;
}

// Check if s[i...j] is palindrome with memoization
private boolean isPalindrome(String s, int i, int j, Boolean[][] memo) {
    // Base case: single character or empty
    if (i >= j) return true;

    // Check memo
    if (memo[i][j] != null) return memo[i][j];

    // Calculate and store result
    boolean result = false;
    if (s.charAt(i) == s.charAt(j)) {
        result = isPalindrome(s, i + 1, j - 1, memo);
    }

    memo[i][j] = result;
    return result;
}

What Happens with `s = "aaa"`:

Check all substrings:

[0,0]: "a" → i >= j → true ✓ (count = 1)
[0,1]: "aa" → 'a' == 'a' && isPalindrome(1,0) → true ✓ (count = 2)
[0,2]: "aaa" → 'a' == 'a' && isPalindrome(1,1) → true ✓ (count = 3)

[1,1]: "a" → i >= j → true ✓ (count = 4)
[1,2]: "aa" → 'a' == 'a' && isPalindrome(2,1) → true ✓ (count = 5)

[2,2]: "a" → i >= j → true ✓ (count = 6)

Total: 6 ✓

Memoization Table:

For "aaa":

memo[i][j]:
     0    1    2
0 [ T    T    T ]  ("a", "aa", "aaa")
1 [      T    T ]  ("a", "aa")
2 [           T ]  ("a")

T = true (palindrome, counted)

Execution Flow Visualization:

Outer loops iterate through all substrings:
i=0, j=0: Check "a" → true → count=1
i=0, j=1: Check "aa"
          → s[0]==s[1]? yes
          → Check inner [1,0] → base case true
          → memo[0][1] = true → count=2
i=0, j=2: Check "aaa"
          → s[0]==s[2]? yes
          → Check inner [1,1] → base case true
          → memo[0][2] = true → count=3
i=1, j=1: Check "a" → true → count=4
i=1, j=2: Check "aa"
          → s[1]==s[2]? yes
          → Check inner [2,1] → base case true
          → memo[1][2] = true → count=5
i=2, j=2: Check "a" → true → count=6

Final count: 6

Complexity:

Time: O(n²) - checking n² substrings, each cell computed once
Space: O(n²) - memo table + O(n) recursion stack

3. Bottom-Up DP (Tabulation - O(n²))

The Intuition

Key Insight: Build solutions from smallest substrings to largest. Count palindromes as we discover them.

Build order:

Length 1: All single characters are palindromes (count them)
Length 2: Check if both characters match (count them)
Length 3+: Use previously computed results (count them)

State: dp[i][j] = true if substring s[i...j] is a palindrome

Transition:

dp[i][j] = (s[i] == s[j]) && (j - i <= 2 || dp[i+1][j-1])

public int countSubstrings(String s) {
    int n = s.length();
    if (n == 0) return 0;

    boolean[][] dp = new boolean[n][n];
    int count = 0;

    // Base case: every single character is a palindrome
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
        count++;  // Count single characters
    }

    // Build by increasing length
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;

            if (s.charAt(i) == s.charAt(j)) {
                // If length is 2 or inner substring is palindrome
                if (len == 2 || dp[i+1][j-1]) {
                    dp[i][j] = true;
                    count++;  // Count this palindrome
                }
            }
        }
    }

    return count;
}

What Happens with `s = "aaa"`:

Step 1: Initialize single characters (length 1)
dp[0][0] = true → count = 1  // "a"
dp[1][1] = true → count = 2  // "a"
dp[2][2] = true → count = 3  // "a"

Step 2: Check length 2
i=0, j=1: s[0]==s[1]? 'a'=='a' ✓
          len==2 → dp[0][1] = true → count = 4  // "aa"
i=1, j=2: s[1]==s[2]? 'a'=='a' ✓
          len==2 → dp[1][2] = true → count = 5  // "aa"

Step 3: Check length 3
i=0, j=2: s[0]==s[2]? 'a'=='a' ✓
          dp[1][1] = true ✓
          → dp[0][2] = true → count = 6  // "aaa"

Final count: 6 ✓

DP Table Evolution:

Initial (length 1):
     0    1    2
0 [ T    -    - ]
1 [      T    - ]
2 [           T ]
count = 3

After length 2:
     0    1    2
0 [ T    T    - ]  ← "aa" found, count = 4
1 [      T    T ]  ← "aa" found, count = 5
2 [           T ]
count = 5

After length 3:
     0    1    2
0 [ T    T    T ]  ← "aaa" found, count = 6
1 [      T    T ]
2 [           T ]
count = 6

Step-by-step with `s = "abc"`:

Step 1: Single characters (length 1)
dp[0][0] = true → count = 1  // "a"
dp[1][1] = true → count = 2  // "b"
dp[2][2] = true → count = 3  // "c"

Step 2: Check length 2
i=0, j=1: s[0]==s[1]? 'a'=='b' ✗ → dp[0][1] = false
i=1, j=2: s[1]==s[2]? 'b'=='c' ✗ → dp[1][2] = false

Step 3: Check length 3
i=0, j=2: s[0]==s[2]? 'a'=='c' ✗ → dp[0][2] = false

Final count: 3 ✓ (only single characters)

Complexity:

Time: O(n²) - two nested loops
Space: O(n²) - dp table only (no recursion stack)

Quick Comparison

Feature	Expand from Center	Memoization	Tabulation
Structure	Iterative + expand	Recursive + cache	Loop + array
Direction	Expand outward	Top-down	Bottom-up
Time	O(n²)	O(n²)	O(n²)
Space	O(1)	O(n²) memo + O(n) stack	O(n²) array only
Counting Logic	Count during expansion	Count after checking	Count during building
When to use	Space-efficient, intuitive	Natural recursion	Classic DP pattern

The Evolution

Approach 1 → Approach 2:

// Instead of expanding, use recursion with memoization
for each substring [i,j]:
    if isPalindrome(i, j, memo):
        count++

Approach 2 → Approach 3:

// Replace recursion with nested loops
for len = 1 to n:
    for i = 0 to n-len:
        j = i + len - 1
        if dp[i][j] is palindrome:
            count++

Mental Models

Expand from Center: "A palindrome is symmetric. Let me check every possible center, expand while characters match, and count each valid palindrome I find."

Memoization: "For each substring [i,j], check if it's a palindrome recursively. Cache results. Count all that are palindromes."

Tabulation: "Build from small to large. Single characters first (count them), then pairs (count palindromes), then triplets (count palindromes), etc. Use previously computed results."

Which Approach to Use?

Use Expand from Center when:

✅ You need O(1) space
✅ You want the most intuitive solution
✅ You prefer iterative over recursive
✅ Counting during expansion feels natural

Use Memoization when:

✅ You want to think recursively
✅ You're comfortable with checking all substrings
✅ You might need the palindrome information for other queries
✅ The recursive structure helps you understand

Use Tabulation when:

✅ You want the classic interval DP pattern
✅ You're learning interval DP systematically
✅ You want to avoid recursion overhead
✅ You prefer iterative building from base cases

Complete Working Example

public class PalindromicSubstrings {

    // Approach 1: Expand from Center
    public int countSubstringsExpand(String s) {
        if (s == null || s.length() == 0) return 0;
        int count = 0;

        for (int i = 0; i < s.length(); i++) {
            count += countPalindromesFromCenter(s, i, i);      // odd
            count += countPalindromesFromCenter(s, i, i + 1);  // even
        }
        return count;
    }

    private int countPalindromesFromCenter(String s, int left, int right) {
        int count = 0;
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            count++;
            left--;
            right++;
        }
        return count;
    }

    // Approach 2: Memoization
    public int countSubstringsMemo(String s) {
        if (s == null || s.length() == 0) return 0;
        int n = s.length();
        Boolean[][] memo = new Boolean[n][n];
        int count = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (isPalindrome(s, i, j, memo)) {
                    count++;
                }
            }
        }
        return count;
    }

    private boolean isPalindrome(String s, int i, int j, Boolean[][] memo) {
        if (i >= j) return true;
        if (memo[i][j] != null) return memo[i][j];

        boolean result = false;
        if (s.charAt(i) == s.charAt(j)) {
            result = isPalindrome(s, i + 1, j - 1, memo);
        }
        memo[i][j] = result;
        return result;
    }

    // Approach 3: Tabulation
    public int countSubstringsDP(String s) {
        int n = s.length();
        if (n == 0) return 0;

        boolean[][] dp = new boolean[n][n];
        int count = 0;

        // Single characters
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
            count++;
        }

        // Build by length
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    if (len == 2 || dp[i+1][j-1]) {
                        dp[i][j] = true;
                        count++;
                    }
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        PalindromicSubstrings ps = new PalindromicSubstrings();

        System.out.println("Test 1: 'abc'");
        System.out.println("Expand from Center: " + ps.countSubstringsExpand("abc")); // 3
        System.out.println("Memoization: " + ps.countSubstringsMemo("abc"));           // 3
        System.out.println("Tabulation: " + ps.countSubstringsDP("abc"));              // 3

        System.out.println("\nTest 2: 'aaa'");
        System.out.println("Expand from Center: " + ps.countSubstringsExpand("aaa")); // 6
        System.out.println("Memoization: " + ps.countSubstringsMemo("aaa"));           // 6
        System.out.println("Tabulation: " + ps.countSubstringsDP("aaa"));              // 6
    }
}

Common Pitfalls

Pitfall 1: Forgetting to count during expansion

// WRONG - only returns length
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
    left--;
    right++;
}
return right - left - 1;  // This gives LENGTH, not COUNT

// RIGHT - count each valid expansion
int count = 0;
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
    count++;  // Count this palindrome!
    left--;
    right++;
}
return count;

Pitfall 2: Not checking both odd and even centers

// WRONG - only checks odd-length palindromes
for (int i = 0; i < n; i++) {
    count += countPalindromesFromCenter(s, i, i);
}

// RIGHT - check both odd and even
for (int i = 0; i < n; i++) {
    count += countPalindromesFromCenter(s, i, i);      // odd: "aba"
    count += countPalindromesFromCenter(s, i, i + 1);  // even: "abba"
}

Pitfall 3: Counting logic in tabulation

// WRONG - counting ALL cells
for (int len = 2; len <= n; len++) {
    for (int i = 0; i <= n - len; i++) {
        int j = i + len - 1;
        dp[i][j] = ...;
        count++;  // Wrong! Counting even if not palindrome
    }
}

// RIGHT - only count when palindrome found
if (s.charAt(i) == s.charAt(j)) {
    if (len == 2 || dp[i+1][j-1]) {
        dp[i][j] = true;
        count++;  // Count only when palindrome confirmed
    }
}

Practice Extensions

Once you master these three approaches, try:

Longest Palindromic Substring (LC 5): Find the longest instead of counting
Longest Palindromic Subsequence (LC 516): Allow non-contiguous characters
Palindrome Partitioning (LC 131): Partition string into palindromic substrings
Palindrome Pairs (LC 336): Find pairs of words that form palindromes

Key Differences from Longest Palindromic Substring

Aspect	Longest Palindromic Substring	Palindromic Substrings
Goal	Find maximum length	Count all palindromes
Return	String (the longest)	Integer (count)
Tracking	Track start/maxLen	Increment count
Expansion	Return length	Return count of palindromes
DP Update	Update max if longer	Increment count if palindrome

Key Takeaways

THE COUNTING PATTERN

Expand from Center: Count each valid palindrome during expansion

Think: "For each center, expand and count"
Best for: O(1) space solution

Memoization: Check all substrings, count palindromic ones

Think: "Is [i,j] palindrome? If yes, count it!"
Best for: Recursive thinking

Tabulation: Build small to large, count as we discover

Think: "Build systematically, count each palindrome found"
Best for: Classic interval DP pattern

Key insight: We're COUNTING all palindromes, not finding the longest!

The Big Picture

Palindromic Substrings is a counting variant of the palindrome pattern.

Master it, and you'll understand:

How to count instead of optimize
The difference between finding max vs counting all
Multiple approaches to the same counting problem
Space-time tradeoffs in palindrome problems

This is your palindrome counting foundation. Build it strong.

Understanding the Problem​

1. Pure Recursion with Expand from Center (O(n²))​

The Intuition​

What Happens with s = "aaa":​

Visualization:​

Complexity:​

2. Top-Down DP (Memoization - O(n²))​

The Intuition​

What Happens with s = "aaa":​

Memoization Table:​

Execution Flow Visualization:​

Complexity:​

3. Bottom-Up DP (Tabulation - O(n²))​

The Intuition​

What Happens with s = "aaa":​

DP Table Evolution:​

Step-by-step with s = "abc":​

Complexity:​

Quick Comparison​

The Evolution​

Approach 1 → Approach 2:​

Approach 2 → Approach 3:​

Mental Models​

Which Approach to Use?​

Use Expand from Center when:​

Use Memoization when:​

Use Tabulation when:​

Complete Working Example​

Common Pitfalls​

Pitfall 1: Forgetting to count during expansion​

Pitfall 2: Not checking both odd and even centers​

Pitfall 3: Counting logic in tabulation​

Practice Extensions​

Key Differences from Longest Palindromic Substring​

Key Takeaways​

The Big Picture​

Understanding the Problem

1. Pure Recursion with Expand from Center (O(n²))

The Intuition

What Happens with `s = "aaa"`:

Visualization:

Complexity:

2. Top-Down DP (Memoization - O(n²))

The Intuition

What Happens with `s = "aaa"`:

Memoization Table:

Execution Flow Visualization:

Complexity:

3. Bottom-Up DP (Tabulation - O(n²))

The Intuition

What Happens with `s = "aaa"`:

DP Table Evolution:

Step-by-step with `s = "abc"`:

Complexity:

Quick Comparison

The Evolution

Approach 1 → Approach 2:

Approach 2 → Approach 3:

Mental Models

Which Approach to Use?

Use Expand from Center when:

Use Memoization when:

Use Tabulation when:

Complete Working Example

Common Pitfalls

Pitfall 1: Forgetting to count during expansion

Pitfall 2: Not checking both odd and even centers

Pitfall 3: Counting logic in tabulation

Practice Extensions

Key Differences from Longest Palindromic Substring

Key Takeaways

The Big Picture