Algorithms to Count the Number of 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”.

Note: The input string length won’t exceed 1000.

Expand around Center Algorithm to Count the Palindroms

A string palindrom is a string that its reverse is exactly the same. There are two kinds of palindroms: abba and abcba. Therefore, there are 2*N-1 kinds of different centers – which we can expand and count if characters at both ends match.

This palindroms algorithm is intuitive and easy to think of – the following C++ implements this idea and the time complexity is O(N^2 where space complexity is O(1) constant.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int countSubstrings(string s) {
        int ans = 0;
        for (int i = 0; i < s.size(); i ++) { // left index
            int j = i, k = i;
            // odd number of palindroms
            while ((j >= 0) && (k < s.size()) && (s[k] == s[j])) { // odd 
                ans ++;
                j --;
                k ++;
            }
            // even number of palindroms
            j = i; k = i + 1;
            while ((j >= 0) && (k < s.size()) && (s[k] == s[j])) { // even
                ans ++;
                j --;
                k ++;
            }            
        }
        return ans;
    }
};

class Solution {
public:
    int countSubstrings(string s) {
        int ans = 0;
        for (int i = 0; i < s.size(); i ++) { // left index
            int j = i, k = i;
            // odd number of palindroms
            while ((j >= 0) && (k < s.size()) && (s[k] == s[j])) { // odd 
                ans ++;
                j --;
                k ++;
            }
            // even number of palindroms
            j = i; k = i + 1;
            while ((j >= 0) && (k < s.size()) && (s[k] == s[j])) { // even
                ans ++;
                j --;
                k ++;
            }            
        }
        return ans;
    }
};

Bruteforce Algorithm to Count the Palindroms Substrings

The most straighforward solution is to bruteforce the possible different sub strings, which is O(N^2), then by checking if a string if palindroms or not – it requires an addition O(N) which sums up to O(N^3) – too slow.

Dynamic Programming Algorithm to Count the Palindroms Substrings

We can speed up the checkin gof palindroms by remembering the answer to its substring. For example, XabbaY has a subproblem which is abba and we know it is a palindrome in previous calculation, so we just need to compare X with Y.

Let’s define F(i, j) to test if the substring from index i to j is a palindrome. By definition, any single character by definition is a palindrome. And if i and j are neighbours, F(i, j) = s[i] == s[j]. Thus, the other calculations of palindroms are based: f[i][j] = (s[i] == s[j]) && (f[i – 1][j + 1])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        vector<vector<bool>> f(n, vector<bool>(n, false));
        for (int i = 0; i < n; ++ i) {
            f[i][i] = true;    // any single character by definition is a palindrome.
        }
        int ans = n;
        for (int i = 0; i < n; ++ i) {
            for (int j = i - 1; j >= 0; -- j) {
                if (i - j == 1) {
                    f[i][j] = (s[i] == s[j]);
                } else {
                    f[i][j] = (s[i] == s[j]) && (f[i - 1][j + 1]);
                }
                if (f[i][j]) ans ++;
            }
        }
        return ans;
    }
};

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        vector<vector<bool>> f(n, vector<bool>(n, false));
        for (int i = 0; i < n; ++ i) {
            f[i][i] = true;    // any single character by definition is a palindrome.
        }
        int ans = n;
        for (int i = 0; i < n; ++ i) {
            for (int j = i - 1; j >= 0; -- j) {
                if (i - j == 1) {
                    f[i][j] = (s[i] == s[j]);
                } else {
                    f[i][j] = (s[i] == s[j]) && (f[i - 1][j + 1]);
                }
                if (f[i][j]) ans ++;
            }
        }
        return ans;
    }
};

O(N^2) space complexity and O(N^2) time for this Dynamic Programming algorithm to count the number of different palindroms substrings.

See also: Teaching Kids Programming – Using Dynamic Programming to Count the Number of Palindrome Substrings

–EOF (The Ultimate Computing & Technology Blog) —