52. Palindromic Substrings

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

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

Solution : (Brute force)

Checking for all possible length

class Solution
{
public:
    bool checkPalin(string s, int start, int end)
    {
        end = end - 1;
        while (start <= end)
        {
            if (s[start] != s[end])
            {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
    
    int countSubstrings(string s)
    {
        int l = s.length();
        if (l == 1)
        {
            return l;
        }
        int count = s.length();

        for (int i = 0; i <= s.length() - 2; i++)
        {
            if (s[i] == s[i + 1])
            {
                count++;
            }
        }

        for (int k = 3; k <= l; k++)
        {
            for (int i = 0; i <= l - k; i++)
            {
                if (checkPalin(s, i, i + k))
                {
                    count++;
                }
            }
        }

        return count;
    }
};

Time Complexity: O(n^3)

Solution : (DP)

class Solution
{
public:
    int countSubstrings(string s)
    {

        int n = s.length();

        vector<vector<int>> v(n, vector<int>(n, 0));

        //All string of length 1
        for (int i = 0; i < n; i++)
        {
            v[i][i] = 1;
        }

        //All string of length 2
        for (int i = 0; i < n - 1; i++)
        {

            if (s[i] == s[i + 1])
            {
                v[i][i + 1] = 1;
            }
        }

        //All string len >=3
        for (int i = 3; i <= n; i++)
        {
            for (int j = 0; j <= n - i; j++)
            {
                if (s[j] == s[j + i - 1])
                {
                    if (v[j + 1][j + i - 2])
                    {
                        v[j][j + i - 1] = 1;
                    }
                }
            }
        }
        
        int count = 0;
        for (int i = 0; i < v.size(); i++)
        {
            for (int j = 0; j < v.size(); j++)
            {
                if (v[i][j] == 1)
                {
                    count++;
                }
            }
        }

        return count;
    }
};

Time Complexity: O(n^2)

Distinct palindromic substrings

Solution: (Similar Approach)

Given a string of lowercase ASCII characters, find all distinct continuous palindromic sub-strings of it.

Input: The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains a string.

Output: Print the count of distinct continuous palindromic sub-strings of it.

Example:
Input:
2
abaaa
geek

Output:
5
4

#include <bits/stdc++.h>
using namespace std;

int main()
{

    int t;
    cin >> t;

    while (t--)
    {
        string str;
        cin >> str;
        int n = str.length();
        unordered_set<string> s;
        vector<vector<int>> dp(n, vector<int>(n, 0));

        //all string to length 1
        for (int i = 0; i < str.length(); i++)
        {
            s.insert(to_string(str[i]));
            dp[i][i] = 1;
        }

        //all string of length 2
        for (int i = 0; i < str.length() - 1; i++)
        {
            if (str[i] == str[i + 1])
            {
                s.insert(str.substr(i, 2));
                dp[i][i + 1] = 1;
            }
        }

        //all string of len>=3
        for (int k = 3; k <= n; k++)
        {
            for (int i = 0; i <= n - k; i++)
            {
                if (str[i] == str[i + k - 1])
                {
                    if (dp[i + 1][i + k - 2])
                    {
                        s.insert(str.substr(i,k));
                        dp[i][i + k - 1] = 1;
                    }
                }
            }
        }

        cout << s.size() << "\n";
    }
    return 0;
}