Given a string, the task is to count all palindromic sub-strings present in it. Length of palindrome sub-string must be greater than or equal to 2. 
Example
Input
N = 5
str = "abaab"
Output
3
Explanation:
All palindrome substring are : "aba" , "aa" , "baab"
Example
Input
N = 7
str = "abbaeae"
Output
4
Explanation:
All palindrome substring are : "bb" , "abba" ,"aea",
"eae"
Expected Time Complexity : O(|S|^{2})
Expected Auxilliary Space : O(|S|^{2})
Constraints:
2<=|S|<=500

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Dynamic programming

Data structures

Starter code: #User function Template for python3

class Solution:

    def CountPS(self, S, N):
        # code here

Solutions:
class Solution:

	def CountPS(self, S, N):
		count = 0
		dp = [[False] * N for _ in range(N)]
		for i in range(N):
			dp[i][i] = True
		for i in range(N - 1):
			if S[i] == S[i + 1]:
				dp[i][i + 1] = True
				count += 1
		for k in range(3, N + 1):
			for i in range(N - k + 1):
				j = i + k - 1
				if S[i] == S[j] and dp[i + 1][j - 1]:
					dp[i][j] = True
					count += 1
		return count


class Solution:

	def CountPS(self, s, n):
		dp = [[0] * n for i in range(n)]
		c = 0
		for k in range(n):
			i = 0
			for j in range(k, n):
				if k == 0:
					dp[i][j] = 1
				elif k == 1:
					if s[i] == s[j]:
						dp[i][j] = 1
						c += 1
				elif s[i] == s[j] and dp[i + 1][j - 1] == 1:
					dp[i][j] = 1
					c += 1
				i += 1
		return c


class Solution:

	def CountPS(self, S, N):
		n = N
		cnt = 0
		for i in range(n):
			l = i
			r = i
			while l >= 0 and r <= n - 1 and (S[l] == S[r]):
				if r - l > 0:
					cnt += 1
				l -= 1
				r += 1
			l = i
			r = i + 1
			while l >= 0 and r <= n - 1 and (S[l] == S[r]):
				cnt += 1
				l -= 1
				r += 1
		return cnt


class Solution:

	def __init__(self):
		self.count = 0

	def expand(self, l, r):
		while l >= 0 and r < len(S) and (S[l] == S[r]):
			if r - l + 1 >= 2:
				self.count += 1
			l -= 1
			r += 1

	def CountPS(self, S, N):
		for i in range(N):
			self.expand(i, i)
			self.expand(i, i + 1)
		return self.count


class Solution:

	def CountPS(self, S, N):
		dp = [[0] * N for i in range(N)]
		c = 0
		for g in range(N):
			i = 0
			for j in range(g, N):
				if g == 0:
					dp[i][j] = 1
				elif g == 1:
					if S[i] == S[j]:
						dp[i][j] = 1
						c += 1
				elif S[i] == S[j] and dp[i + 1][j - 1] == 1:
					dp[i][j] = 1
					c += 1
				i += 1
		return c


class Solution:

	def CountPS(self, s, N):
		res = 0
		for i in range(N):
			l = i - 1
			r = i + 1
			while l >= 0 and r < len(s) and (s[l] == s[r]):
				res += 1
				l -= 1
				r += 1
			(l, r) = (i, i + 1)
			while l >= 0 and r < len(s) and (s[l] == s[r]):
				res += 1
				l -= 1
				r += 1
		return res


class Solution:

	def CountPS(self, S, N):
		dp = [[0 for j in range(N)] for i in range(N)]
		for i in range(N):
			dp[i][i] = 1
		for i in range(1, N):
			if S[i - 1] == S[i]:
				dp[i - 1][i] = 1
		for col in range(2, N):
			i = 0
			j = col
			while i < N and j < N:
				if S[i] == S[j] and dp[i + 1][j - 1] == 1:
					dp[i][j] = 1
				i += 1
				j += 1
		cnt = 0
		for i in range(N):
			for j in range(N):
				if j > i:
					if dp[i][j] == 1:
						cnt += 1
		return cnt


class Solution:

	def CountPS(self, s, N):
		count = 0
		for i in range(len(s)):
			(l, r) = (i, i)
			while l >= 0 and r < len(s) and (s[l] == s[r]):
				if r - l + 1 >= 2:
					count += 1
				l -= 1
				r += 1
			l = i
			r = i + 1
			while l >= 0 and r < len(s) and (s[l] == s[r]):
				if r - l + 1 >= 2:
					count += 1
				l -= 1
				r += 1
		return count


class Solution:

	def CountPS(self, S, N):
		cnt = 0
		dp = [[0 for k in range(N + 1)] for l in range(N + 1)]
		for _ in range(N):
			(i, j) = (0, _)
			while j < N:
				if _ == 0:
					dp[i][j] = True
				if _ == 1:
					if S[i] == S[j]:
						dp[i][j] = True
						cnt += 1
				elif S[i] == S[j] and dp[i + 1][j - 1]:
					dp[i][j] = True
					cnt += 1
				i += 1
				j += 1
		return cnt


class Solution:

	def CountPS(self, S, N):
		c = 0
		for i in range(len(S)):
			subStr = ''
			for j in range(i, len(S)):
				subStr += S[j]
				if subStr[::-1] == subStr and len(subStr) > 1:
					c = c + 1
		return c


class Solution:

	def isPalindrome(self, s, i, j):
		while i <= j:
			if s[i] != s[j]:
				return False
			i += 1
			j -= 1
		return True

	def CountPS(self, S, N):
		count = 0
		for i in range(N):
			for j in range(i + 1, N):
				if self.isPalindrome(S, i, j):
					count += 1
		return count


class Solution:

	def CountPS(self, S, N):
		count = 0
		dp = [[0 for i in range(N + 1)] for j in range(N + 1)]
		for gap in range(N):
			(i, j) = (0, gap)
			while j < N:
				if gap == 0:
					dp[i][j] = True
				if gap == 1:
					if S[i] == S[j]:
						dp[i][j] = True
						count += 1
				elif S[i] == S[j] and dp[i + 1][j - 1]:
					dp[i][j] = True
					count += 1
				i += 1
				j += 1
		return count


class Solution:

	def check(self, S, i, j):
		count = 0
		while (i >= 0 and j < len(S)) and S[i] == S[j]:
			count += 1
			i -= 1
			j += 1
		return count

	def CountPS(self, S, N):
		count = 0
		g = list(S)
		g = list(set(g))
		if len(g) == 1:
			return N * (N - 1) // 2
		for i in range(N - 2):
			odd = self.check(S, i, i + 2)
			count += odd
		for i in range(N - 1):
			even = self.check(S, i, i + 1)
			count += even
		return count


class Solution:

	def CountPS(self, S, N):
		output = 0
		for i in range(1, N):
			j = 1
			while j <= i and j + i <= N:
				s = S[i - j:j + i]
				if S[i - j:j + i] == s[::-1]:
					output += 1
					j += 1
				else:
					break
					j = 1
			j = 1
			while j <= i and j + i + 1 <= N:
				s = S[i - j:j + i + 1]
				if S[i - j:j + i + 1] == s[::-1]:
					output += 1
					j += 1
				else:
					break
		return output


class Solution:

	def CountPS(self, s, N):
		n = len(s)
		vis = set()
		for i in range(n - 1):
			l = i
			r = i
			while l >= 0 and r < n:
				if s[l] == s[r]:
					if r - l + 1 >= 2:
						vis.add((r, l))
				else:
					break
				l -= 1
				r += 1
			l = i
			r = i + 1
			while l >= 0 and r < n:
				if s[l] == s[r]:
					if r - l + 1 >= 2:
						vis.add((r, l))
				else:
					break
				l -= 1
				r += 1
		return len(vis)


class Solution:

	def CountPS(self, s, n):
		count = 0
		for i in range(n):
			(l, r) = (i, i)
			while l >= 0 and r < n and (s[l] == s[r]):
				count += 1
				l -= 1
				r += 1
			(l, r) = (i, i + 1)
			while l >= 0 and r < n and (s[l] == s[r]):
				count += 1
				l -= 1
				r += 1
		return count - n


class Solution:

	def CountPS(self, S, N):
		count1 = 0
		for i in range(N - 1):
			c = S[i]
			for j in range(i + 1, N):
				c += S[j]
				if c == c[::-1]:
					count1 += 1
		return count1


class Solution:

	def CountPS(self, s, n):
		c = 0
		for i in range(0, n - 1):
			sub_s = s[i]
			for j in range(i + 1, n):
				sub_s += s[j]
				if sub_s == sub_s[::-1]:
					c += 1
		return c


class Solution:

	def CountPS(self, S, N):
		count = 0
		for i in range(N - 1):
			(left, right) = (i - 1, i + 1)
			while left >= 0 and right < N and (S[left] == S[right]):
				count += 1
				left -= 1
				right += 1
			if S[i] == S[i + 1]:
				left = i
				right = i + 1
				while left >= 0 and right < N and (S[left] == S[right]):
					count += 1
					left -= 1
					right += 1
		return count


class Solution:

	def check_palin_fast(self, word):
		left = 0
		right = len(word) - 1
		while left < right:
			if word[left] != word[right]:
				return False
			left += 1
			right -= 1
		return True

	def CountPS(self, S, N):
		count = 0
		for num_chars in range(2, N + 1):
			for i in range(N - num_chars + 1):
				word = S[i:i + num_chars]
				if self.check_palin_fast(word):
					count += 1
		return count


class Solution:

	def CountPS(self, s, n):
		count = 0
		for i in range(n - 1):
			arr = s[i]
			for j in range(i + 1, n):
				arr += s[j]
				if arr == arr[::-1]:
					count += 1
		return count


class Solution:

	def fc(self, s, l, r):
		t = 0
		while l >= 0 and r < len(s) and (s[l] == s[r]):
			t += 1
			l -= 1
			r += 1
		return t

	def CountPS(self, S, N):
		c = 0
		for i in range(len(S)):
			c += self.fc(S, i, i) + self.fc(S, i, i + 1)
		return c - N


class Solution:

	def CountPS(self, s, n):
		l = []
		for i in range(n):
			s1 = s[i]
			for j in range(i + 1, n):
				s1 = s1 + s[j]
				if s1 == s1[::-1]:
					l.append(s1)
		return len(l)


class Solution:

	def CountPS(self, S, N):
		c = 0
		for i in range(len(S)):
			p1 = i
			p2 = i
			while p1 >= 0 and p2 < len(S) and (S[p1] == S[p2]):
				if p1 != p2:
					c += 1
				p1 -= 1
				p2 += 1
			p1 = i
			p2 = i + 1
			while p1 >= 0 and p2 < len(S) and (S[p1] == S[p2]):
				c += 1
				p1 -= 1
				p2 += 1
		return c


class Solution:

	def CountPS(self, S, N):
		dp = [[0] * N for i in range(N)]
		c = 0
		for gap in range(N):
			for i in range(N - gap):
				j = i + gap
				if i == j:
					dp[i][j] = 1
				elif S[i] == S[j]:
					if i + 1 == j:
						dp[i][j] = 1
					else:
						dp[i][j] = dp[i + 1][j - 1]
					c += dp[i][j]
		return c


class Solution:

	def CountPS(self, string, N):
		if N == 1:
			return 1
		dp = [[0] * N for _ in range(N)]
		for i in range(N):
			dp[i][i] = 1
		for i in range(N - 1):
			if string[i] == string[i + 1]:
				dp[i][i + 1] = 1
		for length in range(2, N):
			for i in range(N - length):
				if string[i] == string[i + length] and dp[i + 1][i + length - 1]:
					dp[i][i + length] = 1
		return sum([sum(dp[i]) for i in range(N)]) - N


class Solution:

	def findcount(self, s, l, r):
		total = 0
		while l >= 0 and r < len(s) and (s[l] == s[r]):
			total += 1
			l -= 1
			r += 1
		return total

	def CountPS(self, S, N):
		count = 0
		for i in range(len(S)):
			odd = self.findcount(S, i, i)
			even = self.findcount(S, i, i + 1)
			count += odd + even
		return count - N


class Solution:

	def CountPS(self, s, N):
		n = len(s)
		count = 0
		dp = [[False] * n for _ in range(n)]
		for i in range(n):
			dp[i][i] = True
		for i in range(n - 1):
			if s[i] == s[i + 1]:
				dp[i][i + 1] = True
				count += 1
		for sub_len in range(3, n + 1):
			for i in range(n - sub_len + 1):
				j = i + sub_len - 1
				if s[i] == s[j] and dp[i + 1][j - 1]:
					dp[i][j] = True
					count += 1
		return count


class Solution:

	def CountPS(self, st, n):
		ans = 0
		for i in range(n):
			cur = i
			left = i - 1
			right = i + 1
			flag = False
			while left >= 0 and right < n and (st[left] == st[right]):
				flag = True
				left -= 1
				right += 1
				ans += 1
			left = i - 1
			temp = False
			while left >= 0 and cur < n and (st[left] == st[cur]):
				temp = True
				left -= 1
				cur += 1
				ans += 1
		return ans


class Solution:

	def CountPS(self, S, N):
		ans = 0
		for i in range(N):
			(l, r) = (i - 1, i + 1)
			while l >= 0 and r < N and (S[l] == S[r]):
				ans += 1
				l -= 1
				r += 1
			(l, r) = (i, i + 1)
			while l >= 0 and r < N and (S[l] == S[r]):
				ans += 1
				l -= 1
				r += 1
		return ans


def isPali(S, i, j):
	while i <= j:
		if S[i] != S[j]:
			return 0
		i = i + 1
		j = j - 1
	return 1

class Solution:

	def CountPS(self, S, N):
		count = 0
		for i in range(0, N):
			for j in range(i + 1, N):
				count = count + isPali(S, i, j)
		return count


class Solution:

	def CountPS(self, S, N):
		opt = [[False for _ in range(N)] for _ in range(N)]
		count = 0
		for i in range(N):
			opt[i][i] = True
		for i in range(N - 1, -1, -1):
			for j in range(i + 1, N):
				if S[i] == S[j]:
					if j - i == 1 or opt[i + 1][j - 1]:
						count += 1
						opt[i][j] = True
		return count


class Solution:

	def CountPS(self, S, N):

		def func(S, i, j):
			while i <= j:
				if S[i] != S[j]:
					return 0
				i += 1
				j -= 1
			return 1
		ans = 0
		for i in range(N):
			for j in range(i + 1, N):
				ans += func(S, i, j)
		return ans


class Solution:

	def CountPS(self, S, N):
		count = 0
		dp = [[False for i in range(len(S))] for j in range(len(S))]
		for k in range(len(S)):
			i = 0
			j = k
			while j < len(S):
				if k == 0:
					dp[i][j] = True
				elif k == 1:
					if S[i] == S[j]:
						count += 1
						dp[i][j] = True
					else:
						dp[i][j] = False
				elif S[i] == S[j] and dp[i + 1][j - 1] is True:
					count += 1
					dp[i][j] = True
				else:
					dp[i][j] = False
				i += 1
				j += 1
		return count


class Solution:

	def CountPS(self, S, N):

		def count_palindrome_substrings(string):
			n = len(string)
			dp = [[False for _ in range(n)] for _ in range(n)]
			count = 0
			for i in range(n):
				dp[i][i] = True
				count += 1
			for i in range(n - 1):
				if string[i] == string[i + 1]:
					dp[i][i + 1] = True
					count += 1
			for k in range(3, n + 1):
				for i in range(n - k + 1):
					j = i + k - 1
					if string[i] == string[j] and dp[i + 1][j - 1]:
						dp[i][j] = True
						count += 1
			return count
		p = count_palindrome_substrings(S)
		return p - len(S)


class Solution:

	def CountPS(self, S, N):

		def substrings(S, i, j):
			if i >= j:
				return 1
			if S[i] == S[j]:
				return substrings(S, i + 1, j - 1)
			else:
				return 0
		ans = 0
		for i in range(N):
			for j in range(i, N):
				ans += substrings(S, i, j)
		return ans - N


class Solution:

	def CountPS(self, S, N):
		c = 0
		for i in range(N):
			temp = ''
			for j in range(i, N):
				temp += S[j]
				r = 0
				l = len(temp) - 1
				f = True
				while r < l:
					if temp[r] != temp[l]:
						f = False
						break
					r = r + 1
					l = l - 1
				if f and len(temp) > 1:
					c += 1
		return c


class Solution:

	def CountPS(self, s, n):
		ans = 0
		for i in range(n):
			l = r = i
			while l >= 0 and r < n and (s[l] == s[r]):
				if r - l + 1 >= 2:
					ans += 1
				l -= 1
				r += 1
			l = i
			r = i + 1
			while l >= 0 and r < n and (s[l] == s[r]):
				if r - l + 1 >= 2:
					ans += 1
				l -= 1
				r += 1
		return ans


class Solution:

	def CountPS(self, s, n):
		n = len(s)
		dp = [[0 for j in range(n)] for i in range(n)]
		cnt = 0
		for i in range(n):
			dp[i][i] = 1
		for i in range(n - 1):
			if s[i] == s[i + 1]:
				dp[i][i + 1] = 1
				cnt += 1
		for k in range(3, n + 1):
			for i in range(n - k + 1):
				j = i + k - 1
				if s[i] == s[j] and dp[i + 1][j - 1] == 1:
					dp[i][j] = 1
					cnt += 1
		return cnt


class Solution:

	def CountPS(self, S, N):
		ans = 0
		for i in range(N):
			left = i
			right = i + 1
			while left >= 0 and right < N:
				if S[left] == S[right]:
					ans += 1
					left -= 1
					right += 1
				else:
					break
			left = i - 1
			right = i + 1
			while left >= 0 and right < N:
				if S[left] == S[right]:
					ans += 1
					left -= 1
					right += 1
				else:
					break
		return ans


class Solution:

	def CountPS(self, S, N):
		n = N
		s = S
		dp = [[False for _ in range(n)] for _ in range(n)]
		for i in range(n):
			dp[i][i] = True
		count = 0
		for length in range(1, n):
			for i in range(n - length):
				j = i + length
				if s[i] == s[j] and (j - i <= 2 or dp[i + 1][j - 1]):
					dp[i][j] = True
					count += 1
		return count


class Solution:

	def CountPS(self, S, N):
		i = 0
		k = 0
		l = 0
		m = 0
		x = 0
		y = 0
		for i in range(N):
			j = i + 1
			while j < N:
				x = i
				y = j
				flag = False
				while i <= j:
					if S[i] != S[j]:
						break
					i = i + 1
					j = j - 1
				if i > j:
					k = k + 1
				i = x
				j = y + 1
		return k


class Solution:

	def CountPS(self, s, N):
		n = len(s)
		dp = [[False] * n for i in range(n)]
		ans = 0
		for g in range(n):
			i = 0
			for j in range(g, n):
				if g == 0:
					dp[i][j] = True
				elif g == 1:
					if s[i] == s[j]:
						dp[i][j] = True
					else:
						dp[i][j] = False
				elif s[i] == s[j] and dp[i + 1][j - 1] == True:
					dp[i][j] = True
				else:
					dp[i][j] = False
				if dp[i][j] == True:
					ans += 1
				i += 1
		return ans - len(s)


class PalInfo:

	def __init__(self):
		self.nb = 0
		self.max_len = 1

class Solution:

	def CountPS(self, s, n):
		pals = [PalInfo() for _ in range(len(s))]
		res = 0
		for i in range(1, len(s)):
			while i - pals[i].max_len >= 0 and s[i] == s[i - pals[i].max_len]:
				pals[i].nb += 1
				pals[i].max_len += 1
			if i > 0 and s[i] != s[i - 1]:
				if i >= 2 and s[i] == s[i - 2]:
					pals[i].nb += 1
					pals[i].max_len += 2
			if pals[i - 1].max_len != 1:
				candidate_idx = i - pals[i - 1].max_len - 1
				if candidate_idx >= 0 and s[i] == s[candidate_idx]:
					pals[i].nb += 1
					pals[i].max_len = pals[i - 1].max_len + 2
			res += pals[i].nb
		return res


class Solution:

	def CountPS(self, S, N):
		count = 0
		for i in range(1, N):
			p1 = i
			p2 = i - 1
			shift = 1
			while p1 - shift in range(0, N) and p1 + shift in range(0, N) and (S[p1 - shift] == S[p1 + shift]):
				count += 1
				shift += 1
			shift = 0
			while p1 + shift in range(0, N) and p2 - shift in range(0, N) and (S[p1 + shift] == S[p2 - shift]):
				count += 1
				shift += 1
			shift = 0
		return count


class Solution:

	def CountPS(self, S, N):
		c = 0
		for i in range(N):
			j = i
			k = i
			while j >= 0 and k < N and (S[j] == S[k]):
				d = k - j + 1
				if d >= 2:
					c += 1
				j -= 1
				k += 1
			j = i
			k = i + 1
			while j >= 0 and k < N and (S[j] == S[k]):
				d = k - j + 1
				if d >= 2:
					c += 1
				j -= 1
				k += 1
		return c


class Solution:

	def CountPS(self, s, n):
		dp = [[False for i in range(n)] for j in range(n)]
		c = 0
		for a in range(n):
			i = 0
			j = a
			while j < n:
				if i == j:
					dp[i][j] = True
				elif i == j - 1 and s[i] == s[j]:
					dp[i][j] = True
					c += 1
				elif s[i] == s[j] and dp[i + 1][j - 1]:
					dp[i][j] = True
					c += 1
				i += 1
				j += 1
		return c


class Solution:

	def CountPS(self, S, N):
		N = len(S)
		mp = {}
		dp = [[0 for i in range(N)] for i in range(N)]
		ans = 0
		for i in range(N):
			dp[i][i] = 1
		for l in range(2, N):
			for i in range(N - l + 1):
				j = i + l - 1
				if l == 2:
					if S[i] == S[j]:
						ans += 1
						dp[i][j] = 1
				elif S[i] == S[j] and dp[i + 1][j - 1] == 1:
					ans += 1
					dp[i][j] = 1
		i = 0
		j = N - 1
		if S[i] == S[j] and dp[i + 1][j - 1] == 1:
			ans += 1
			dp[i][j] = 1
		if N == 2 and S[i] == S[j]:
			ans += 1
		return ans


class Solution:

	def CountPS(self, s, n):

		def isPalindrome(s, i, j):
			if i > j:
				return False
			while i < j:
				if s[i] != s[j]:
					return False
				i += 1
				j -= 1
			return True
		ct = 0
		for i in range(n):
			for j in range(i + 1, n):
				if isPalindrome(s, i, j):
					ct += 1
		return ct


class Solution:

	def CountPS(self, S, N):
		c = 0
		for i in range(N):
			l = i - 1
			r = i + 1
			while l >= 0 and r <= N - 1:
				if S[l] == S[r]:
					c += 1
				else:
					break
				l -= 1
				r += 1
		for i in range(N):
			l = i
			r = i + 1
			while l >= 0 and r <= N - 1:
				if S[l] == S[r]:
					c += 1
				else:
					break
				l -= 1
				r += 1
		return c


class Solution:

	def CountPS(self, S, N):

		def solve(low, high, s):
			ans = int()
			while low >= 0 and high < len(s) and (s[low] == s[high]):
				low -= 1
				high += 1
				if high - (low + 1) >= 2:
					ans += 1
			return ans
		ans = int()
		for i in range(N):
			ans += solve(i, i, S)
			ans += solve(i, i + 1, S)
		return ans


ps = {}

def isPalindromic(s):
	if s in ps:
		return ps[s]
	if len(s) < 2:
		return True
	if s[0] == s[-1]:
		t = isPalindromic(s[1:-1])
		ps[s] = t
		return t
	ps[s] = False
	return False

class Solution:

	def CountPS(self, S, N):
		digs = {}
		count = 0
		for i in range(N):
			if i < N - 1:
				k = S[i:i + 2]
				if isPalindromic(k):
					count += 1
					digs[i] = [k]
			if i < N - 2:
				k = S[i:i + 3]
				if isPalindromic(k):
					count += 1
					if i in digs:
						digs[i].append(k)
					else:
						digs[i] = [k]
		while len(digs) > 0:
			newdigs = {}
			for d in digs:
				t = digs[d]
				for tt in t:
					temp = len(tt)
					if d > 0 and temp + d < N:
						newd = S[d - 1:temp + d + 1]
						if not isPalindromic(newd):
							continue
						count += 1
						if d - 1 not in newdigs:
							newdigs[d - 1] = [newd]
						else:
							newdigs[d - 1].append(newd)
			digs = newdigs.copy()
		return count


class Solution:

	def CountPS(self, S, N):
		ss = [[-1 for i3 in range(N)] for i4 in range(N)]
		count = 0
		for i2 in range(N):
			ss[i2][i2] = 1
			count += 1
		for i in range(1, N):
			c = i
			for k in range(N - i):
				if S[c] == S[k]:
					if ss[c - 1][k + 1] == 1 or ss[c - 1][k + 1] == -1:
						ss[c][k] = 1
						count += 1
					else:
						ss[c][k] = 0
				else:
					ss[c][k] = 0
				c += 1
		return count - N


class Solution:

	def CountPS(self, S, N):
		dp = []
		count = 0
		for i in range(N):
			dp.append([None] * N)
		for g in range(N):
			i = 0
			for j in range(g, N):
				if g == 0:
					dp[i][j] = True
					count += 1
				elif g == 1:
					if S[i] == S[j]:
						dp[i][j] = True
						count += 1
					else:
						dp[i][j] = False
				elif S[i] == S[j] and dp[i + 1][j - 1] == True:
					dp[i][j] = True
					count += 1
				else:
					dp[i][j] = False
				i += 1
		return count - N


class Solution:

	def CountPS(self, s, n):
		dp = []
		for i in range(n):
			dp.append([0] * n)
		c = 0
		for g in range(n):
			i = 0
			for j in range(g, n):
				if g == 0:
					dp[i][j] = 1
				elif g == 1:
					if s[i] == s[j]:
						dp[i][j] = 1
					else:
						dp[i][j] = 0
				if g > 1:
					if s[i] == s[j] and dp[i + 1][j - 1] == 1:
						dp[i][j] = 1
					else:
						dp[i][j] = 0
				if dp[i][j] == 1:
					c += 1
				i += 1
		return c - n