How to find all palindromic substrings

Given a string, count how many palindromic substrings in the given string

A palindrome is a string that reads the same backward as forward. For instance, level, baab

Example 1

Input:   abc

Output:  3

Example 2

Input:   aaa

Output:  6

Explanation: a, a, a, aa, aa, aaa

This problem is the continuation of the problem: How to find the longest palindromic substring. To solve this problem, we will use the same technique - palindrome expansion.

Approach

To count how many palindromic substrings, we can try to use each character and pair as a middle of a palindrome and try to expand the palindrome. On each step of expansion, we will check if a new string is a palindrome or not. Let's see the approach step by step.

1. Take the first character as a middle of a palindrome
2. Try to add one character to the left and one to the right
   • if, after adding characters, we still have a palindrome
     • continue to add characters and increment the palindromes counter
   • if was not able to add characters or the substring is not a palindrome
     • try to use another character as a middle of a palindrome

Code

    public int CountPalindromicSubstrings(string text)
    {
        if (string.IsNullOrEmpty(text))
        {
            return 0;
        }

        int[] result = new int[1];
        for (int i = 0; i < text.Length; i++)
        {
            CountPalindrome(text, i, i, result);
            CountPalindrome(text, i, i + 1, result);
        }

        return result[0];
    }

    private static void CountPalindrome(string text, int lo, int hi, int[] result)
    {
        while (lo >= 0 && hi < text.Length && text[lo] == text[hi])
        {
            result[0]++;
            lo--;
            hi++;
        }
    }

The time complexity is O(n^2).