Palindromic Substrings

MediumDynamic ProgrammingString
Category: 1-D Dynamic Programming
Companies that ask this question:
FacebookAmazonGoogleMicrosoft

Approach

Palindromic Substrings

Problem Statement

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: Ten palindromic strings: "r", "a", "c", "e", "c", "a", "r", "cec", "aceca", "racecar".

Constraints

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

Approach

This problem can be solved using several approaches, with the Expand Around Center technique being the most intuitive and efficient for this specific problem.

Approach 1: Expand Around Center

Intuition

A palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only 2n - 1 such centers (n single-character centers for odd-length palindromes and n-1 two-character centers for even-length palindromes).

Algorithm Steps

  1. For each possible center (0 to n-1):
    • Expand for odd-length palindromes (center, center)
    • Expand for even-length palindromes (center, center+1)
  2. For each expansion:
    • While left and right characters match and are within bounds
    • Count this palindrome and expand outward (left--, right++)
  3. Return total count

Example Walkthrough

For s = "aba":

  • Center 0: "a" (odd) → count = 1
  • Centers 0-1: no match (even) → count = 1
  • Center 1: "b" (odd), then "aba" (odd) → count = 3
  • Centers 1-2: no match (even) → count = 3
  • Center 2: "a" (odd) → count = 4

Total: 4 palindromic substrings

Approach 2: Dynamic Programming

Intuition

We can use DP where dp[i][j] represents whether substring s[i...j] is a palindrome.

State Definition

dp[i][j] = true if s[i...j] is a palindrome, false otherwise

Base Cases

  • dp[i][i] = true (single character)
  • dp[i][i+1] = (s[i] == s[i+1]) (two characters)

Recurrence Relation

dp[i][j] = (s[i] == s[j]) AND dp[i+1][j-1]

For a substring to be a palindrome:

  1. First and last characters must match
  2. Inner substring must also be a palindrome

Approach 3: Manacher's Algorithm

Intuition

Manacher's algorithm is an advanced O(n) solution that cleverly uses previously computed information to avoid redundant checks.

It transforms the string to handle both odd and even length palindromes uniformly and maintains the rightmost palindrome boundary to optimize computations.

Complexity Analysis

Expand Around Center

  • Time Complexity: O(n²)

    • n centers to check
    • Each expansion can take up to n steps in the worst case

  • Space Complexity: O(1)

    • Only using a few variables

Dynamic Programming

  • Time Complexity: O(n²)

    • Filling an n × n DP table

  • Space Complexity: O(n²)

    • DP table of size n × n

Manacher's Algorithm

  • Time Complexity: O(n)

    • Each position is visited at most twice

  • Space Complexity: O(n)

    • Array to store palindrome radii

Key Insights

  1. Two Types of Centers: Must check both odd-length and even-length palindromes
  2. Early Termination: Stop expanding when characters don't match or bounds are reached
  3. Counting vs Finding: We only need to count, not store all palindromes
  4. Space-Time Tradeoff: Expand Around Center uses O(1) space but O(n²) time

Common Pitfalls

  1. Forgetting Even-Length Palindromes: Must check centers between characters
  2. Off-by-One Errors: Carefully handle array bounds during expansion
  3. Overcounting: Each palindrome should be counted exactly once
  4. Starting Points: In DP, must process shorter substrings before longer ones

Comparison of Approaches

| Approach | Time | Space | Difficulty | Recommended | |----------|------|-------|------------|-------------| | Expand Around Center | O(n²) | O(1) | Easy | ⭐ Best for this problem | | Dynamic Programming | O(n²) | O(n²) | Medium | Good for learning | | Manacher's Algorithm | O(n) | O(n) | Hard | Overkill for most cases |

Related Problems

  • Longest Palindromic Substring (LeetCode 5)
  • Palindrome Pairs (LeetCode 336)
  • Valid Palindrome (LeetCode 125)
  • Longest Palindromic Subsequence (LeetCode 516)

Tips

  • For interviews, Expand Around Center is the preferred solution
  • DP approach is useful if you need to know which substrings are palindromes
  • Manacher's is primarily for competitive programming or when optimization is critical

Tags

  • String
  • Dynamic Programming
  • Two Pointers
  • Medium

Solution

java
1class Solution {
2    // Approach 1: Expand Around Center
3    // Time: O(n^2), Space: O(1)
4    public int countSubstrings(String s) {
5        int count = 0;
6        int n = s.length();
7
8        for (int center = 0; center < n; center++) {
9            // Odd-length palindromes
10            count += expandAroundCenter(s, center, center);
11
12            // Even-length palindromes
13            count += expandAroundCenter(s, center, center + 1);
14        }
15
16        return count;
17    }
18
19    private int expandAroundCenter(String s, int left, int right) {
20        int count = 0;
21
22        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
23            count++;
24            left--;
25            right++;
26        }
27
28        return count;
29    }
30
31    // Approach 2: Dynamic Programming
32    // Time: O(n^2), Space: O(n^2)
33    public int countSubstringsDP(String s) {
34        int n = s.length();
35        boolean[][] dp = new boolean[n][n];
36        int count = 0;
37
38        // Every single character is a palindrome
39        for (int i = 0; i < n; i++) {
40            dp[i][i] = true;
41            count++;
42        }
43
44        // Check for two-character palindromes
45        for (int i = 0; i < n - 1; i++) {
46            if (s.charAt(i) == s.charAt(i + 1)) {
47                dp[i][i + 1] = true;
48                count++;
49            }
50        }
51
52        // Check for palindromes of length 3 or more
53        for (int len = 3; len <= n; len++) {
54            for (int i = 0; i <= n - len; i++) {
55                int j = i + len - 1;
56
57                if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
58                    dp[i][j] = true;
59                    count++;
60                }
61            }
62        }
63
64        return count;
65    }
66
67    // Approach 3: Manacher's Algorithm (Advanced)
68    // Time: O(n), Space: O(n)
69    public int countSubstringsManacher(String s) {
70        // Transform string to handle even-length palindromes
71        String transformed = "#";
72        for (char c : s.toCharArray()) {
73            transformed += c + "#";
74        }
75
76        int n = transformed.length();
77        int[] p = new int[n]; // p[i] = radius of palindrome centered at i
78        int center = 0;
79        int right = 0;
80        int count = 0;
81
82        for (int i = 0; i < n; i++) {
83            int mirror = 2 * center - i;
84
85            if (i < right) {
86                p[i] = Math.min(right - i, p[mirror]);
87            }
88
89            // Expand around center i
90            int a = i + (1 + p[i]);
91            int b = i - (1 + p[i]);
92
93            while (a < n && b >= 0 && transformed.charAt(a) == transformed.charAt(b)) {
94                p[i]++;
95                a++;
96                b--;
97            }
98
99            // Update center and right boundary
100            if (i + p[i] > right) {
101                center = i;
102                right = i + p[i];
103            }
104
105            // Count palindromic substrings
106            count += (p[i] + 1) / 2;
107        }
108
109        return count;
110    }
111}
112
Loading visualizer...