[Google Question] Number of Palindromic Substrings

Problem: Given a string, your task is to count how many palindromic substrings in this string. It is given that substrings with different start index and end index are different substrings even if they contains exactly same characters. For example if given string is "nnn" then "[nn]n" and "n[nn]" are different substrings.

Example:

Input: "aaabab"
Output: 11
Explanation: Eleven palindromic strings: "a", "a", "a", "b", "a", "b", "aa", "aa", "aaa", "aba", "bab"

Approach: We can use the same approach which we used in Longest Palindromic Substring where we choose every possible center for potential (even length and odd length) palindromes. Instead of calculating the length, here we are going to increment a counter when we found a palindrome.

That's all!

Implementation in C#:

    public int CountSubstrings(string s) 

    {

        if (s?.Length == 0)

        {

            return 0;

        }

        // Initial count is 1 for the character at 0th index

        int countPalindromicSubStrings = 1;

        for (int index = 1; index < s.Length; ++index)

        {

            ++countPalindromicSubStrings; // Every character is itself a palindrome

            // Odd Palindromes

            int i = index - 1;

            int j = index + 1;

            while (i >= 0 && j < s.Length && s[i] == s[j])

            {

                ++countPalindromicSubStrings;

                --i;

                ++j;

            }

            // Even Palindromes

            i = index - 1;

            j = index;

            while (i >= 0 && j < s.Length && s[i] == s[j])

            {

                ++countPalindromicSubStrings;

                --i;

                ++j;

            }

        }

        return countPalindromicSubStrings;

    }

Complexity: O(n^2)