647. Number of palindromic substring

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:

1. The input string length won't exceed 1000.

Thoughts:

1. Explanation by GeeksforGeeks (with extension problem to output all the substrings)
2. for loop with O(n^2) solution: having a pivot as a midpoint of palindrome and expand it in both directions to find all palindromes of even and odd lengths.

3. O(n) with Manacher’s algorithm

Code:

class Solution {
public:
    int countSubstrings(string s) {
        int ans = 0, n = s.length();
        for(int i = 0; i < n; ++i){
             // odd: substring s[i-j, ..., i+j],
             // i is the middle index of the substring; 
            for(int j = 0; i - j >= 0 && i + j < n
             && s[i - j] == s[i + j]; j++) ans++;
            // even: substring s[i-1-j, ..., i+j], 
            // (i-1, i) is the middle index of the substring;
            for(int j = 0; i - j  >= 0 && i + j + 1< n
             && s[i - j ] == s[i + j + 1]; j++) ans++;
        }

        return ans;
    }
};

Special thanks to caihao0727mail for providing this solution.

Code: Interesting implementation using round-off

int countSubstrings(string s) {
    int num = s.size();
    for(float center = 0.5; center < s.size(); center += 0.5) {
        int left = int(center - 0.5), right = int(center + 1);
        while(left >= 0 && right < s.size() &&
         s[left--] == s[right++]) ++num;
    }
    return num;
}

center 0.5: 0 1
center 1: 0 2
center 1.5: 1 2
center 2: 1 3
center 2.5: 2 3
center 3: 2 4
center 3.5: 3 4
center 4: 3 5
center 4.5: 4 5

Code: Manacher's Algorithm: O(n) !

class Solution(object):
    def countSubstrings(self, S):
        def manachers(S):
            A = '@#' + '#'.join(S) + '#$'
            Z = [0] * len(A)
            print "%s\n%s"%(A,Z)
            center = right = 0
            for i in xrange(1, len(A) - 1):
                # get the palindrome numbers based on right boundary 
                # and mirror palindrome 
                if i < right:
                    Z[i] = min(right - i, Z[2 * center - i])

                # expand the palindrome at current pivot
                while A[i + Z[i] + 1] == A[i - Z[i] - 1]:
                    Z[i] += 1

                    # update right boundary
                if i + Z[i] > right:
                    center, right = i, i + Z[i]
            return Z

        return sum((v+1)/2 for v in manachers(S))

Special thanks to hellokenlee for providing this solution.