Vultr DocsLatest Content

Palindromic Substrings

Updated on 20 June, 2025
Palindromic Substrings header image

Problem Statement

The challenge is to determine how many substrings within a given string s are palindromes. A palindrome is defined as a sequence of characters that reads the same forward and backward. A substring, meanwhile, refers to any contiguous sequence of characters within the string. This task involves not only identifying individual palindromic characters but also discovering larger sequences that fulfill the palindrome condition.

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".

Constraints

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

Approach and Intuition

Let's break down the execution strategy for counting palindromic substrings, inspired by the examples and constraints provided:

  1. Understanding Palindromes in Context:

    • Each single character in a string is, by default, a palindrome. Therefore, in a string of length n, there are at least n palindromic substrings (each character by itself).
    • The challenge increases as we consider longer substrings for palindrome checks.

  2. Strategies to Identify Palindromes:

    • Brute Force Approach: This involves generating all possible substrings and checking if each one is a palindrome. This method, however, could be inefficient given that the number of substrings of a string of length n is n(n+1)/2.
    • Expand Around Center Technique: A more efficient approach could be exploring each potential center of a palindrome and expanding outwards to check for palindromic conditions. This handles both odd and even length palindromes effectively.
    • Example illustration:
      • For the string "aaa", choosing 'a' as the center and expanding:
        • Single a's are palindromes.
        • Expanding around the first 'a', we get "aa" (a palindrome).
        • Continuing with "aaa" gives another palindrome.
      • This approach ends up checking significantly fewer substrings directly by leveraging the symmetry of palindromes.

  3. Complexity Analysis and Constraints Consideration:

    • Given s.length <= 1000, our optimal approach should aim for a time complexity closer to O(n^2) rather than the cubic time that the brute force method might take.
    • The implementation should handle edge cases like strings consisting of a single character or repetitive characters efficiently since the string only consists of lowercase English letters (simplifying character comparisons).

Solutions

  • C++
  • Java
cpp 
class Solution {
 public:
    int computeTotalPalindromes(string str) {
        int total = 0;

        for (int i = 0; i < str.length(); ++i) {
            total += expandAroundCenter(str, i, i);
            total += expandAroundCenter(str, i, i + 1);
        }

        return total;
    }

    int expandAroundCenter(const string& s, int left, int right) {
        int count = 0;

        while (left >= 0 and right < s.length()) {
            if (s[left] != s[right])
                break;

            left--;
            right++;
            count++;
        }

        return count;
    }
};

This C++ solution effectively counts the palindromic substrings within a given string. It employs a technique that expands around potential centers of palindromes to check for symmetry. The primary function computeTotalPalindromes initializes a count of palindromic substrings (total) and iterates through each character in the string, treating each as a potential center.

The helper function expandAroundCenter is utilized for checking the symmetry around either a single character (odd length palindromes) or a pair of characters (even length palindromes). This function adjusts the left and right pointers to expand outward from the center until the symmetry is broken or the bounds of the string are reached, counting each symmetric expansion as a valid palindromic substring.

For each index in the string:

  • Expand around the single center character to count odd-length palindromes.
  • Expand around two consecutive characters to count even-length palindromes.

The operations performed ensure that all palindromic substrings are counted efficiently, making this approach both straightforward and versatile for different string lengths.

java 
class Solution {
    public int countSubstrings(String s) {
        int result = 0;

        for (int i = 0; i < s.length(); ++i) {
            result += findPalindromes(s, i, i);
            result += findPalindromes(s, i, i + 1);
        }

        return result;
    }

    private int findPalindromes(String str, int left, int right) {
        int count = 0;

        while (left >= 0 && right < str.length()) {
            if (str.charAt(left) != str.charAt(right))
                break;

            left--;
            right++;
            count++;
        }

        return count;
    }
}

The provided Java program efficiently counts palindromic substrings within a given string. The solution centers around the principle of expanding around potential centers of palindromes – both single characters and pairs of characters.

  • The countSubstrings method iterates over each character of the string. For each character position, it acts as a potential palindrome center in two scenarios:

    • It considers the character itself as the center.
    • It also considers the gap between the current character and the next as a potential even-length palindrome center.

  • During each iteration, the method findPalindromes is invoked twice:

    • First, with parameters pointing to the same character (odd-length palindrome).
    • Second, with parameters pointing to adjacent characters (even-length palindrome).

  • The findPalindromes method further explores each center by expanding outwards. Expansion continues as long as characters at the expanding positions match and the bounds of the string are respected.

  • This expansion process leverages a two-pointer approach:

    • The pointers start at the specified positions and move outward symmetrically.
    • If the characters at these pointers match, the palindrome count is incremented, and the process continues.
    • The loop breaks when a mismatch is found, or the pointers exceed the boundary of the string.

  • This algorithm ensures each palindrome center is checked, making the method both comprehensive and efficient. The approach of expanding from the center reduces the need for redundant checks, making it optimal for counting palindrome substrings.

Comments

No comments yet.