# given a string s, count the number of palindrom in it
# for ex "hellolle", 1) "ellolle" , 2) "lol" 3)"lloll", 4) "ll", 5) "ll"
# also each letter would be regarded as palindrom, so total is 13
# "wowpurerocks", output 14, ( each letter + "wow" and "rer")


class Solution(object):
    def countPalindrom(self, S):
        l = len(S)
        dp = [[0] * l for _ in xrange(l)]

        for i in xrange(l):
            dp[i][i] = 1

        for i in reversed(xrange(l - 1)):
            for j in xrange(i + 1, l):
                if S[i] == S[j]:
                    if i + 1 == j:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i + 1][j - 1]

        return sum(map(sum, dp))


if __name__ == '__main__':
    print Solution().countPalindrom("hellolle")
    print Solution().countPalindrom("wowpurerocks")
