Palindromic Substrings

medium
Dynamic ProgrammingStringDynamic Programming

Given a string s, return the total number of palindromic substrings in it. A substring is a contiguous sequence of characters within the string. A palindrome reads the same forwards and backwards. Substrings at different positions are counted separately even if they consist of the same characters.

Examples

Example 1

  • Input: s = "abc"
  • Output: 3
  • Explanation: The three palindromic substrings are "a", "b", and "c".

Example 2

  • Input: s = "aaa"
  • Output: 6
  • Explanation: The six palindromic substrings are "a", "a", "a", "aa", "aa", and "aaa".

Constraints

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

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Expand Around Center

Intuition

Every palindrome has a center point. For odd-length palindromes the center is a single character, and for even-length palindromes the center is between two adjacent characters. We iterate through all possible centers and expand outward as long as the characters on both sides match. Each successful expansion corresponds to one palindromic substring. Since there are 2n - 1 possible centers and each expansion takes at most O(n) time, this is an efficient O(n^2) solution with constant space.

Algorithm

  1. Initialize a counter to zero.
  2. For each index `i` in the string, expand around center for odd-length palindromes (`left = i, right = i`).
  3. For each index `i`, also expand around center for even-length palindromes (`left = i, right = i + 1`).
  4. During each expansion, while `left >= 0`, `right < n`, and `s[left] == s[right]`, increment the counter and continue expanding.
  5. Return the total count.
TimeO(n^2)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        int count = 0;

        auto expand = [&](int left, int right) {
            while (left >= 0 && right < n && s[left] == s[right]) {
                count++;
                left--;
                right++;
            }
        };

        for (int i = 0; i < n; i++) {
            expand(i, i);
            expand(i, i + 1);
        }

        return count;
    }
};
Java 21
class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        int count = 0;

        for (int i = 0; i < n; i++) {
            count += expand(s, i, i);
            count += expand(s, i, i + 1);
        }

        return count;
    }

    private int expand(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;
    }
}
Python 3.12
class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        count = 0

        def expand(left: int, right: int) -> int:
            total = 0
            while left >= 0 and right < n and s[left] == s[right]:
                total += 1
                left -= 1
                right += 1
            return total

        for i in range(n):
            count += expand(i, i)
            count += expand(i, i + 1)

        return count
Go 1.26
func countSubstrings(s string) int {
    n := len(s)
    count := 0

    expand := func(left, right int) int {
        total := 0
        for left >= 0 && right < n && s[left] == s[right] {
            total++
            left--
            right++
        }
        return total
    }

    for i := 0; i < n; i++ {
        count += expand(i, i)
        count += expand(i, i+1)
    }

    return count
}
Approach 2

Dynamic Programming

Intuition

We use a 2D boolean table where dp[i][j] indicates whether the substring s[i..j] is a palindrome. Single characters are always palindromes. For two-character substrings, we check if both characters match. For longer substrings, s[i..j] is a palindrome if s[i] == s[j] and dp[i+1][j-1] is true. We count every cell that is marked true.

Algorithm

  1. Create a 2D boolean array `dp` of size `n x n`, initialized to false.
  2. Initialize count to zero.
  3. Mark all single characters as palindromes (`dp[i][i] = true`) and increment count for each.
  4. Check all substrings of length 2: set `dp[i][i+1] = true` if `s[i] == s[i+1]` and increment count.
  5. For lengths 3 to n, set `dp[i][j] = true` if `s[i] == s[j]` and `dp[i+1][j-1]` is true, incrementing count for each palindrome found.
  6. Return the total count.
TimeO(n^2)SpaceO(n^2)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        int count = 0;

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

        for (int i = 0; i < n - 1; i++) {
            if (s[i] == s[i + 1]) {
                dp[i][i + 1] = true;
                count++;
            }
        }

        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s[i] == s[j] && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    count++;
                }
            }
        }

        return count;
    }
};
Java 21
class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int count = 0;

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

        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                count++;
            }
        }

        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    count++;
                }
            }
        }

        return count;
    }
}
Python 3.12
class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        count = 0

        for i in range(n):
            dp[i][i] = True
            count += 1

        for i in range(n - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = True
                count += 1

        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
Go 1.26
func countSubstrings(s string) int {
    n := len(s)
    dp := make([][]bool, n)
    for i := range dp {
        dp[i] = make([]bool, n)
    }
    count := 0

    for i := 0; i < n; i++ {
        dp[i][i] = true
        count++
    }

    for i := 0; i < n-1; i++ {
        if s[i] == s[i+1] {
            dp[i][i+1] = true
            count++
        }
    }

    for length := 3; length <= n; length++ {
        for i := 0; i <= n-length; i++ {
            j := i + length - 1
            if s[i] == s[j] && dp[i+1][j-1] {
                dp[i][j] = true
                count++
            }
        }
    }

    return count
}

Frequently asked questions

What is the optimal time complexity of Palindromic Substrings?

The most efficient approach in this guide ("Dynamic Programming") runs in O(n^2) time and uses O(n^2) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Palindromic Substrings use?

Palindromic Substrings is a medium-level Dynamic Programming problem involving String, Dynamic Programming. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Palindromic Substrings be solved without extra space?

The most space-efficient approach in this guide uses O(n^2) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(1), while the optimized version uses O(n^2).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Related Problems

Longest Palindromic Substring

Original problem: leetcode.com

Loading editor...
Input
s=
"abc"
Expected Output
3