Palindromic Substrings

This question is the cousin of “Longest Palindromic Substring”. Same idea, slightly different goal. Here we do not want the longest one. We want to count how many there are. So the same center trick works, but instead of saving the best piece, we add one to a counter each time we find a palindrome.

🎯 The Problem

You get a string. You count every piece that is a palindrome. A palindrome is text that reads the same forwards and backwards, like “aaa” or “aba”.

The rules:

• Count every continuous piece that reads the same both ways.
• Even a single letter counts as a palindrome.
• Two pieces at different positions count as different, even if they look the same.

For "aaa", the singles give “a”, “a”, “a”. The pairs give “aa”, “aa”. The whole thing gives “aaa”. So the total is six.

Input:  s = "aaa"
Output: 6

Explanation: "a", "a", "a", "aa", "aa", "aaa" are all palindromes.

Here is the problem drawn out. We are counting all the mirror-like pieces inside the string.

🐢 Approach 1: Check Every Piece (Brute Force)

The idea in one line: test every piece and add one to the count for each palindrome.

The idea:

• Pick a start. Pick an end. That gives one piece.
• Walk that piece from both ends to test it.
• If every pair of letters matches, count it.

How it works:

• Two nested loops pick the start and the end.
• A third walk tests each piece.

Why it is weak:

• Picking start and end is O(n²) on its own.
• Each test adds another walk of up to n steps.
• Total time is about O(n³). It drags on a long string.
• You keep re-checking the same letters.

Here is the brute-force code for that idea:

def count_substrings(s):
    count = 0
    for left in range(len(s)):
        for right in range(left, len(s)):
            candidate = s[left:right + 1]
            if candidate == candidate[::-1]:
                count += 1
    return count

📊 Approach 2: Dynamic Programming Table (Better)

The idea in one line: a longer piece is a palindrome only if its inside is one and its two ends match.

The idea:

• Dynamic programming saves answers to small pieces so we never solve them twice.
• Mark each piece as palindrome or not in a table.
• Count each piece that the table marks true.

How it works:

• Single letters are palindromes. Two equal letters are too.
• A piece i..j is a palindrome when s[i] == s[j] and the inside i+1..j-1 already is.
• Fill from short pieces to long pieces, adding one to the count for each true mark.

Why it is weak:

• It needs a full table of size n by n.
• That costs O(n²) memory for no extra speed.
• Time is O(n²), same as the next idea, but it uses far more memory.

Here is the DP-table code for that idea:

def count_substrings(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    count = 0

    for length in range(1, n + 1):
        for left in range(n - length + 1):
            right = left + length - 1
            if s[left] == s[right] and (length <= 2 or dp[left + 1][right - 1]):
                dp[left][right] = True
                count += 1

    return count

⚡ Approach 3: Expand Around Center And Count (Best)

The idea in one line: every palindrome has a center, so grow from each center and count one for every match.

The idea:

• A palindrome has a center: a single letter, or a gap between two letters.
• Stand at a center and push left and right outwards.
• Each time the two ends match, that whole window is a new, larger palindrome.

How it works:

• Try a single-letter center for odd length palindromes.
• Try the gap to the next letter for even length palindromes.
• While the left letter equals the right letter, add one to the count, then grow.

Why it is fast:

• Each successful step outward is itself one more palindrome, so we count as we grow.
• There are about 2n centers, each growing up to n steps, so time is O(n²).
• It keeps only a counter, so extra memory is O(1).

Here is the counting dry run on "aaa" for one center.

Steps to Solve

1. Start a counter at zero.
2. Walk through the string. Treat each index as a possible center.
3. For each index, expand around a single-letter center for odd length palindromes.
4. For each index, also expand around the gap to the next letter for even length palindromes.
5. While the left letter equals the right letter, add one to the counter, then move left back and right forward.
6. After checking every center, return the counter.

#include <stdio.h>
#include <string.h>

// count palindromes that grow from one center
int expand(const char *s, int n, int left, int right) {
    int count = 0;
    while (left >= 0 && right < n && s[left] == s[right]) {
        count++;       // one more palindrome found
        left--;
        right++;
    }
    return count;
}

int countSubstrings(const char *s) {
    int n = (int)strlen(s);
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += expand(s, n, i, i);      // odd length center
        total += expand(s, n, i, i + 1);  // even length center
    }
    return total;
}

int main(void) {
    const char *s = "aaa";
    printf("%d\n", countSubstrings(s));
    return 0;
}

6

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

int expand(const string& s, int left, int right) {
    int count = 0;
    int n = (int)s.size();
    while (left >= 0 && right < n && s[left] == s[right]) {
        count++;       // one more palindrome found
        left--;
        right++;
    }
    return count;
}

int countSubstrings(const string& s) {
    int total = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        total += expand(s, i, i);      // odd length center
        total += expand(s, i, i + 1);  // even length center
    }
    return total;
}

int main() {
    string s = "aaa";
    cout << countSubstrings(s) << endl;
    return 0;
}

6

public class PalindromicSubstrings {
    static int expand(String s, int left, int right) {
        int count = 0;
        int n = s.length();
        while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
            count++;       // one more palindrome found
            left--;
            right++;
        }
        return count;
    }

    static int countSubstrings(String s) {
        int total = 0;
        for (int i = 0; i < s.length(); i++) {
            total += expand(s, i, i);      // odd length center
            total += expand(s, i, i + 1);  // even length center
        }
        return total;
    }

    public static void main(String[] args) {
        String s = "aaa";
        System.out.println(countSubstrings(s));
    }
}

6

def count_substrings(s):
    total = 0

    def expand(left, right):
        count = 0
        # grow outwards while both ends match
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1   # one more palindrome found
            left -= 1
            right += 1
        return count

    for i in range(len(s)):
        total += expand(i, i)      # odd length center
        total += expand(i, i + 1)  # even length center

    return total


s = "aaa"
print(count_substrings(s))

6

function countSubstrings(s) {
  let total = 0;

  function expand(left, right) {
    let count = 0;
    // grow outwards while both ends match
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      count++; // one more palindrome found
      left--;
      right++;
    }
    return count;
  }

  for (let i = 0; i < s.length; i++) {
    total += expand(i, i);     // odd length center
    total += expand(i, i + 1); // even length center
  }

  return total;
}

const s = "aaa";
console.log(countSubstrings(s));

6

Let us read the Python version line by line. Saying this out loud in an interview shows you really understand the counting.

We begin with total = 0. This holds the running count of palindromes.

The expand helper takes a left and a right index. Inside, count starts at zero. The while loop checks that left stays inside the string, that right stays inside the string, and that the two letters match. While all three hold, we found one more palindrome, so we do count += 1. Then we move left back and right forward to grow the window.

Why does each step add a palindrome? Because every time the ends match, the whole window from left to right is a fresh, larger palindrome. So one match equals one new palindrome.

When the loop stops, we return count. That is how many palindromes share this exact center.

In the main loop we call expand(i, i) for the odd case, where a single letter is the center. We also call expand(i, i + 1) for the even case, where the gap between two letters is the center. We add both counts to total.

Finally we return total. For "aaa" the odd centers give four and the even centers give two, so the answer is six.

⏱️ Time and Space Complexity

The brute force checks every piece and re-walks each one, so it is O(n³). Expand around center visits about 2n centers and grows each up to n steps, so it is O(n²) with O(1) extra memory. The dynamic programming version is also O(n²) but it needs an O(n²) table. So expand around center wins on memory.

🧩 Key Takeaways

• ✅ Every single letter counts as a palindrome, so the count is never zero for a non-empty string.
• ✅ Each step outward from a matching center is itself a new, larger palindrome to count.
• ✅ Expand for both odd centers and even centers at every position.
• ✅ The expand-around-center count runs in O(n²) time with O(1) extra memory.
• ✅ It is the same trick as the longest palindrome problem, just counting instead of saving.

🚀 What’s Next?

• Longest Palindromic Substring
• Encode and Decode Strings