Palindromic Substrings (LC 647): Expand Around Center

Count every palindromic substring of a string, where equal text at different positions counts separately. Interval DP works in O(n^2) time and space; expanding around all 2n-1 centers keeps O(n^2) time with O(1) space.

Language Selection

Choose your preferred programming language

Showing: Python

Palindromic Substrings

Problem Statement

You are given a string s. Count how many of its substrings are palindromes, meaning they read the same forwards and backwards.

A substring is a contiguous, non-empty run of characters. Two substrings are counted separately when they start or end at different positions, even if their text is identical. So in "bb" the two single "b" characters are two different substrings.

Examples

Example 1:

Input: s = "xyz"
Output: 3
Explanation: No two neighbouring characters match, so only the single letters "x", "y" and "z" are palindromes.

Example 2:

Input: s = "bbbb"
Output: 10
Explanation: Every substring is a palindrome: 4 of length 1, 3 of length 2 ("bb"),
2 of length 3 ("bbb") and 1 of length 4 ("bbbb"). 4 + 3 + 2 + 1 = 10.

Example 3:

Input: s = "level"
Output: 7
Explanation: The 5 single letters, plus "eve" and "level".

Constraints

  • 1 <= s.length <= 1000
  • s contains only lowercase English letters.

Approach 1: Interval Dynamic Programming

Algorithm

A substring s[i..j] is a palindrome exactly when its two end characters match and the part strictly inside, s[i+1..j-1], is also a palindrome (an empty or one-character inside counts as a palindrome). That gives a recurrence on intervals:

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

dp[i][j] depends on dp[i+1][j-1], a row below it, so we fill the table with i going from the end of the string back to the start, and j going forward from i.

  1. Create an n x n boolean table dp, all false.
  2. For i from n - 1 down to 0, and for j from i up to n - 1:
    • If s[i] == s[j] and either j - i < 2 or dp[i+1][j-1] is true, set dp[i][j] = true and add 1 to the count.
  3. Return the count.

Implementation

Python:

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        # dp[i][j] is True when s[i..j] is a palindrome
        dp = [[False] * n for _ in range(n)]
        count = 0
        # i runs backwards so dp[i + 1][j - 1] is already filled
        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                if s[i] == s[j] and (j - i < 2 or dp[i + 1][j - 1]):
                    dp[i][j] = True
                    count += 1
        return count

Java:

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        // dp[i][j] is true when s[i..j] is a palindrome
        boolean[][] dp = new boolean[n][n];
        int count = 0;
        // i runs backwards so dp[i + 1][j - 1] is already filled
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    count++;
                }
            }
        }
        return count;
    }
}

Go:

func countSubstrings(s string) int {
    n := len(s)
    // dp[i][j] is true when s[i..j] is a palindrome
    dp := make([][]bool, n)
    for i := range dp {
        dp[i] = make([]bool, n)
    }
    count := 0
    // i runs backwards so dp[i+1][j-1] is already filled
    for i := n - 1; i >= 0; i-- {
        for j := i; j < n; j++ {
            if s[i] == s[j] && (j-i < 2 || dp[i+1][j-1]) {
                dp[i][j] = true
                count++
            }
        }
    }
    return count
}

JavaScript:

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {
    const n = s.length;
    // dp[i][j] is true when s[i..j] is a palindrome
    const dp = Array.from({ length: n }, () => new Array(n).fill(false));
    let count = 0;
    // i runs backwards so dp[i + 1][j - 1] is already filled
    for (let i = n - 1; i >= 0; i--) {
        for (let j = i; j < n; j++) {
            if (s[i] === s[j] && (j - i < 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                count++;
            }
        }
    }
    return count;
};

C#:

public class Solution {
    public int CountSubstrings(string s) {
        int n = s.Length;
        // dp[i, j] is true when s[i..j] is a palindrome
        bool[,] dp = new bool[n, n];
        int count = 0;
        // i runs backwards so dp[i + 1, j - 1] is already filled
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s[i] == s[j] && (j - i < 2 || dp[i + 1, j - 1])) {
                    dp[i, j] = true;
                    count++;
                }
            }
        }
        return count;
    }
}

C++:

#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        // dp[i][j] is true when s[i..j] is a palindrome
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        int count = 0;
        // i runs backwards so dp[i + 1][j - 1] is already filled
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    count++;
                }
            }
        }
        return count;
    }
};

Complexity Analysis

  • Time: O(n^2). There are n(n+1)/2 pairs (i, j) with i <= j, and each is decided in O(1) from a value already in the table.
  • Space: O(n^2) for the n x n table.

Approach 2: Expand Around Center (Optimal)

Algorithm

Every palindrome has a center. An odd-length palindrome is centered on one character, and an even-length palindrome is centered on the gap between two characters. A string of length n has n character centers and n - 1 gap centers, so 2n - 1 centers in total.

From each center, grow outwards one step at a time. Each successful step (the two new end characters match) finds exactly one new palindrome. The first mismatch ends that center, because any longer substring with the same center contains the mismatched pair.

  1. For each center index c from 0 to 2n - 2:
    • Set left = c / 2 and right = left + c % 2. Even c is the character c / 2; odd c is the gap after it.
    • While left >= 0, right < n and s[left] == s[right]: add 1 to the count, then move left one step left and right one step right.
  2. Return the count.

Implementation

Python:

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        count = 0
        # 2n - 1 centers: even c is a character, odd c is the gap after s[c // 2]
        for center in range(2 * n - 1):
            left = center // 2
            right = left + center % 2
            # Every matching expansion step is one more palindrome
            while left >= 0 and right < n and s[left] == s[right]:
                count += 1
                left -= 1
                right += 1
        return count

Java:

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        int count = 0;
        // 2n - 1 centers: even c is a character, odd c is the gap after s[c / 2]
        for (int center = 0; center < 2 * n - 1; center++) {
            int left = center / 2;
            int right = left + center % 2;
            // Every matching expansion step is one more palindrome
            while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                count++;
                left--;
                right++;
            }
        }
        return count;
    }
}

Go:

func countSubstrings(s string) int {
    n := len(s)
    count := 0
    // 2n - 1 centers: even c is a character, odd c is the gap after s[c/2]
    for center := 0; center < 2*n-1; center++ {
        left := center / 2
        right := left + center%2
        // Every matching expansion step is one more palindrome
        for left >= 0 && right < n && s[left] == s[right] {
            count++
            left--
            right++
        }
    }
    return count
}

JavaScript:

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {
    const n = s.length;
    let count = 0;
    // 2n - 1 centers: even c is a character, odd c is the gap after s[c / 2]
    for (let center = 0; center < 2 * n - 1; center++) {
        let left = Math.floor(center / 2);
        let right = left + (center % 2);
        // Every matching expansion step is one more palindrome
        while (left >= 0 && right < n && s[left] === s[right]) {
            count++;
            left--;
            right++;
        }
    }
    return count;
};

C#:

public class Solution {
    public int CountSubstrings(string s) {
        int n = s.Length;
        int count = 0;
        // 2n - 1 centers: even c is a character, odd c is the gap after s[c / 2]
        for (int center = 0; center < 2 * n - 1; center++) {
            int left = center / 2;
            int right = left + center % 2;
            // Every matching expansion step is one more palindrome
            while (left >= 0 && right < n && s[left] == s[right]) {
                count++;
                left--;
                right++;
            }
        }
        return count;
    }
}

C++:

#include <string>
using namespace std;

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        int count = 0;
        // 2n - 1 centers: even c is a character, odd c is the gap after s[c / 2]
        for (int center = 0; center < 2 * n - 1; center++) {
            int left = center / 2;
            int right = left + center % 2;
            // Every matching expansion step is one more palindrome
            while (left >= 0 && right < n && s[left] == s[right]) {
                count++;
                left--;
                right++;
            }
        }
        return count;
    }
};

Complexity Analysis

  • Time: O(n^2). There are 2n - 1 centers and each expands at most about n / 2 steps. The worst case is a string of one repeated letter, where every expansion runs until it hits an edge.
  • Space: O(1). Only a few integer variables are used.

Key Insights

  • Count by center, not by substring. Checking all O(n^2) substrings one by one costs O(n) each, O(n^3) total. Grouping substrings by their center lets each check reuse the one inside it, so each palindrome costs O(1).
  • One expansion step equals one palindrome. That is why the count goes up inside the loop instead of once per center.
  • Two kinds of center. Odd lengths center on a character and even lengths center on a gap. Forgetting the gaps misses every even palindrome such as "bb".
  • The DP and the expansion use the same fact. s[i..j] is a palindrome if and only if s[i] == s[j] and s[i+1..j-1] is one. The DP stores those answers; the expansion walks them in order and needs no table.
  • The answer fits in a 32-bit int. At most n(n+1)/2 = 500,500 substrings exist for n = 1000.

Edge Cases

  1. Single character: the answer is 1.
  2. All characters distinct, like "xyz": the answer is n, only the single letters.
  3. One repeated letter, like "bbbb": every substring counts, so the answer is n(n+1)/2. This is also the slowest input for both approaches.
  4. Two characters: 2 if they differ, 3 if they match.
  5. Equal text at different positions, like the two "b"s in "abba": each occurrence counts.

Common Mistakes

  1. Skipping even-length centers. Expanding only from characters returns 4 instead of 6 for "abba".
  2. Counting distinct palindromes. Putting substrings in a set answers a different question, since repeated text must be counted again.
  3. Filling the DP table in the wrong order. Looping i forward reads dp[i+1][j-1] before it is computed. Loop i backwards, or loop by substring length.
  4. Reading dp[i+1][j-1] for short substrings. When j - i < 2 the inside is empty or one character, and for j == i the index i+1 > j-1 points at an unfilled cell. Short-circuit with j - i < 2 first.
  5. Continuing after a mismatch. Once s[left] != s[right], no longer palindrome shares that center, so stop expanding.

Interview Tips

  1. Clarify what counts. Confirm that substrings are contiguous and that equal text at different positions is counted twice.
  2. Start from the O(n^3) idea in a sentence, then explain the reuse that brings it to O(n^2).
  3. Code the expansion version. It is short, uses O(1) space, and is hard to get wrong once you handle both center kinds.
  4. Walk through "abba" out loud. It exercises single letters, a gap center ("bb", then "abba") and a failed expansion.
  5. Mention Manacher’s algorithm as the O(n) answer if asked for better, but say you would only code it if required.

Follow-up Questions

  1. Return the longest palindrome instead of the count? Same expansion, but track the widest range. See Longest Palindromic Substring below.
  2. Can you do better than O(n^2)? Manacher’s algorithm finds the palindrome radius at every center in O(n) by reusing radii inside a known palindrome; the count is the sum of (radius + 1) / 2 over centers in the transformed string.
  3. Count only distinct palindromic substrings? A palindromic tree (eertree) does this in O(n); a set of substrings also works for small inputs.
  4. Count palindromic subsequences instead of substrings? That needs a different interval DP, because subsequences can skip characters.
  5. Split the string into the fewest palindromes? Precompute the dp table from Approach 1, then run a one-dimensional DP over cut positions.