Count of palindromic substrings in a string in C++

Problem statement:

Given a string, the task is to count the number of palindromic substrings present in this string. If any 2 substrings are identical but they have different starting or ending index, then they are considered to be different

Example 1:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

---

Palindromes:

Palindromes are the sequence of characters that reads the same forward and backward. To read more about it, click here.

ex: aaaa, abba, 56765

---

Naive approach:

Simply, generate all the substrings of the given string and check whether they are palindrome or not. If they are palindrome, increment the count value by 1 and simply return the count value.

Since checking a string for palindrome takes linear time and generating all substrings of a string takes quadratic time so, total time complexity will be cubic. Submitting a solution with cubic time complexity on an online judge will obviously lead to TLE.

---

Optimized approach:

Idea is to count all the palindrome substrings with odd and even lengths. We can do so by taking every index as a midpoint.

• In the case of odd length palindromes, fix the current index position as the center and iterate in both directions until we hit any extreme end position or the character on the right side of the center index is different than that of the character on the left side.
• For even length palindrome, we take center as the current index and compare it with the character on just one index lower than the center. we keep on iterating to the left side character and right side character and comparing them.

C++ implementation of the above concept:

#include<bits/stdc++.h>
using namespace std;
int countSubstrings(string s) {
    int tps = 0, odd, even;
    int n = s.length();
    for (int i = 0; i < n; i++)
    {
        odd = 1;
        while (i - odd >= 0 && i + odd < n && s[i - odd] == s[i + odd]) // for calculating odd-length palindromes with  centres s[i]
        {
            odd++;
        }
        even = 0;
        while (i - even - 1 >= 0 && i + even < n && s[i - even - 1] == s[i + even]) //for calculating even-length palindromes with  centres s[i]
        {
            even++;
        }
        tps += (odd + even);
    }
    return tps;
}

int main()
{
    string s;
    cin >> s;
    cout << countSubstrings(s);
    return 0;
}

If this post added any value to your algorithmic knowledge, please share your valuable feedback in the comment section below. Thank you!