Given a string str of lowercase ASCII characters, Count the number of distinct continuous palindromic sub-strings which are present in the string str.
Example 1:
Input:
str = "abaaa"
Output:
5
Explanation : These are included in answer:
"a","aa","aaa","aba","b"
Example 2:
Input
str = "geek"
Output: 
4
Explanation : Below are 4 palindrome sub-strings
"e","ee","g","k"
Your Task:
You don't need to read input or print anything. Your task is to complete the function palindromeSubStrs() which takes the string str as input parameter and returns the total number of distinct continuous palindromic sub-strings in str.
Expected Time Complexity : O(N^{2}logN)
Expected Auxilliary Space : O(N^{2})
Constraints:
1 ≤ N ≤ 3*10^{3}, where N is the length of the string str.

Difficulty: MEDIUM_HARD
Tags: String algorithms

Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures
Expected Time Complexity: O(N^{2}logN)
Expected Auxiliary Space: O(N^{2})

Starter code:
#User function Template for python3



class Solution:

    def palindromeSubStrs(self, Str):

        # code here

Solutions:
class Solution:

	def palindromeSubStrs(self, s):
		m = dict()
		n = len(s)
		R = [[0 for x in range(n + 1)] for x in range(2)]
		s = '@' + s + '#'
		for j in range(2):
			rp = 0
			R[j][0] = 0
			i = 1
			while i <= n:
				while s[i - rp - 1] == s[i + j + rp]:
					rp += 1
				R[j][i] = rp
				k = 1
				while R[j][i - k] != rp - k and k < rp:
					R[j][i + k] = min(R[j][i - k], rp - k)
					k += 1
				rp = max(rp - k, 0)
				i += k
		s = s[1:len(s) - 1]
		m[s[0]] = 1
		for i in range(1, n):
			for j in range(2):
				for rp in range(R[j][i], 0, -1):
					m[s[i - rp - 1:i - rp - 1 + 2 * rp + j]] = 1
			m[s[i]] = 1
		return len(m)


class Solution:

	def palindromeSubStrs(self, str):
		l = len(str)
		ls = [0 for i in range(2 * l + 2)]
		a = '@#'
		for i in str:
			a += i
			a += '#'
		a += '@'
		s = set()
		for i in range(2, l * 2 + 2):
			while a[i - ls[i] - 1] == a[i + ls[i] + 1] and (a[i - ls[i] - 1] != '@' or a[i + ls[i] + 1] != '@'):
				ls[i] += 1
				if a[i] == '#' and ls[i] != 0:
					m = i // 2 - ls[i] // 2
					n = i // 2 + ls[i] // 2
					b = str[m:n]
					s.add(b)
				elif a[i] != '#' and ls[i] != 0:
					m = i // 2 - ls[i] // 2 - 1
					n = i // 2 + ls[i] // 2
					b = str[m:n]
					s.add(b)
				if a[i] != '#' and a[i] != '@' and (ls[i] != 0):
					s.add(a[i])
		if '' in s:
			s.remove('')
		return len(s)


class Solution:

	def palindromeSubStrs(self, st):
		s = set()
		n = len(st)
		ans = 0
		for i in range(n):
			l = i
			r = i + 1
			while l >= 0 and r <= n:
				string = st[l:r]
				if string != string[::-1]:
					break
				s.add(string)
				l -= 1
				r += 1
		for i in range(n):
			l = i
			r = i + 2
			while l >= 0 and r <= n:
				string = st[l:r]
				if string != string[::-1]:
					break
				s.add(string)
				l -= 1
				r += 1
		return len(s)


class Solution:

	def palindromeSubStrs(self, s):
		setti = set()
		n = len(s)
		for i in range(n):
			left = i
			right = i + 1
			while left >= 0 and right <= n:
				string = s[left:right]
				if string != string[::-1]:
					break
				setti.add(string)
				left -= 1
				right += 1
		for i in range(n):
			left = i
			right = i + 2
			while left >= 0 and right <= n:
				string = s[left:right]
				if string != string[::-1]:
					break
				setti.add(string)
				left -= 1
				right += 1
		return len(setti)


class Solution:

	def palindromeSubStrs(self, s):
		res = set()
		for i in range(len(s)):
			l = i
			h = i
			while l >= 0 and h < len(s) and (s[l] == s[h]):
				res.add(s[l:h + 1])
				l -= 1
				h += 1
			l = i
			h = i + 1
			while l >= 0 and h < len(s) and (s[l] == s[h]):
				res.add(s[l:h + 1])
				l -= 1
				h += 1
		return len(res)


class Solution:

	def palindromeSubStrs(self, s):
		l = []
		n = s
		res = n[0]
		m = 0
		dp = [[0] * len(n) for _ in range(len(n))]
		for i in range(len(n)):
			dp[i][i] = 1
			res = n[i:i + 1]
			if res not in l:
				l.append(res)
		for i in range(len(n) - 1):
			if n[i] == n[i + 1]:
				dp[i][i + 1] = 1
				res = n[i:i + 2]
				if res not in l:
					l.append(res)
		for j in range(2, len(n)):
			for i in range(len(n) - j):
				if n[i] == n[i + j] and dp[i + 1][i + j - 1] == 1:
					dp[i][i + j] = dp[i + 1][i + j - 1]
					res = n[i:i + j + 1]
					if res not in l:
						l.append(res)
		return len(l)


class Solution:

	def expand(self, Str, i, j, p):
		while i >= 0 and j <= len(Str) - 1 and (Str[i] == Str[j]):
			p.add(Str[i:j + 1])
			i -= 1
			j += 1

	def palindromeSubStrs(self, Str):
		p = set()
		for i in range(len(Str)):
			self.expand(Str, i, i, p)
			self.expand(Str, i, i + 1, p)
		return len(p)


class Solution:

	def palindromeSubStrs(self, s):
		n = len(s)
		p = [[False] * n for i in range(n)]
		d = {}
		r = 0
		for i in s:
			if i not in d:
				d[i] = 1
				r += 1
		for i in range(n):
			p[i][i] = True
		for i in range(n - 1):
			if s[i] == s[i + 1]:
				p[i][i + 1] = True
				if s[i:i + 2] not in d:
					d[s[i:i + 2]] = 1
					r += 1
		for x in range(2, n):
			for i in range(n - x):
				j = x + i
				if s[i] == s[j] and p[i + 1][j - 1]:
					p[i][j] = True
					if s[i:j + 1] not in d:
						d[s[i:j + 1]] = 1
						r += 1
		return r


class Solution:

	def palindromeSubStrs(self, s):
		n = len(s)
		store = set()
		for i in range(n):
			l = r = i
			while l >= 0 and r < n and (s[l] == s[r]):
				store.add(s[l:r + 1])
				l -= 1
				r += 1
			l = i
			r = i + 1
			while l >= 0 and r < n and (s[l] == s[r]):
				store.add(s[l:r + 1])
				l -= 1
				r += 1
		return len(store)


class Solution:

	def palindromeSubStrs(self, Str):
		res = set()
		i = 0
		n = len(Str)
		while i < n:
			j = i - 1
			k = i + 1
			res.add(Str[i])
			while j >= 0 and k < n and (Str[j] == Str[k]):
				res.add(Str[j:k + 1])
				j -= 1
				k += 1
			j = i
			k = i + 1
			while j >= 0 and k < n and (Str[j] == Str[k]):
				res.add(Str[j:k + 1])
				j -= 1
				k += 1
			i += 1
		return len(res)


class Solution:

	def palindromeSubStrs(self, S):
		res = ''
		m = 0
		n = len(S)
		s = set()
		for i in range(n):
			l = i
			r = i
			while l >= 0 and r < n and (S[l] == S[r]):
				s.add(S[l:r + 1])
				l -= 1
				r += 1
			l = i
			r = i + 1
			while l >= 0 and r < n and (S[l] == S[r]):
				s.add(S[l:r + 1])
				l -= 1
				r += 1
		return len(s)


class Solution:

	def palindromeSubStrs(self, Str):
		result = []
		for i in range(len(Str)):
			l = i
			r = i
			while l >= 0 and r < len(Str) and (Str[l] == Str[r]):
				if Str[l:r + 1] not in result:
					result.append(Str[l:r + 1])
				l -= 1
				r += 1
			l = i
			r = i + 1
			while l >= 0 and r < len(Str) and (Str[l] == Str[r]):
				if Str[l:r + 1] not in result:
					result.append(Str[l:r + 1])
				l -= 1
				r += 1
		return len(result)


class Solution:

	def palindromeSubStrs(self, Str):
		l = len(Str)
		d = {}
		for i in range(l):
			j = i
			k = i
			while j >= 0 and k < l and (Str[j] == Str[k]):
				d[Str[j:k + 1]] = 1
				j -= 1
				k += 1
			j = i
			k = i + 1
			while j >= 0 and k < l and (Str[j] == Str[k]):
				d[Str[j:k + 1]] = 1
				j -= 1
				k += 1
		return len(d)


class Solution:

	def palindromeSubStrs(self, Str):
		l = len(Str)
		d = {}
		for i in range(l):
			left = i
			right = i
			while left >= 0 and right < l and (Str[left] == Str[right]):
				d[Str[left:right + 1]] = 1
				left -= 1
				right += 1
			left = i
			right = i + 1
			while left >= 0 and right < l and (Str[left] == Str[right]):
				d[Str[left:right + 1]] = 1
				left -= 1
				right += 1
			i += 1
		return len(d)


class Solution:

	def palindromeSubStrs(self, s):
		n = len(s)
		se = set()
		for i in range(n):
			j = i - 1
			k = i + 1
			r = s[i]
			se.add(r)
			while j >= 0 and k < n and (s[j] == s[k]):
				r = s[j] + r + s[k]
				se.add(r)
				j -= 1
				k += 1
			j = i
			k = i + 1
			r = ''
			while j >= 0 and k < n and (s[j] == s[k]):
				r = s[j] + r + s[k]
				se.add(r)
				j -= 1
				k += 1
		return len(se)


class Solution:

	def palindromeSubStrs(self, Str):
		res = set()

		def distinct(s):
			for i in range(len(s)):
				(l, r) = (i, i)
				count_palindromes(s, l, r)
				(l, r) = (i, i + 1)
				count_palindromes(s, l, r)
			return len(res)

		def count_palindromes(s, l, r):
			while l >= 0 and r < len(s) and (s[l] == s[r]):
				res.add(s[l:r + 1])
				l -= 1
				r += 1
		return distinct(Str)


class Solution:

	def palindromeSubStrs(self, s):
		seen = set()

		def getPalCounts(l, r):
			count = 0
			while l >= 0 and r < len(s) and (s[l] == s[r]):
				cur = s[l:r + 1]
				if cur not in seen:
					count += 1
					seen.add(cur)
				l -= 1
				r += 1
			return count
		res = 0
		for i in range(len(s)):
			res += getPalCounts(i, i)
			res += getPalCounts(i, i + 1)
		return res


class Solution:

	def palindromeSubStrs(self, s):
		n = len(s)

		def expand(i, j):
			while i >= 0 and j < n and (s[i] == s[j]):
				res.add(s[i:j + 1])
				i -= 1
				j += 1
		res = set()
		for i in range(n):
			expand(i, i)
			expand(i, i + 1)
		return len(res)


class Solution:

	def palindromeSubStrs(self, S):
		s = set()
		N = len(S)
		ans = 0
		for k in range(N):
			i = k
			j = k
			while i >= 0 and j < N and (S[i] == S[j]):
				if S[i:j + 1] not in s:
					s.add(S[i:j + 1])
					ans += 1
				i -= 1
				j += 1
		for k in range(N - 1):
			i = k
			j = k + 1
			while i >= 0 and j < N and (S[i] == S[j]):
				if S[i:j + 1] not in s:
					s.add(S[i:j + 1])
					ans += 1
				i -= 1
				j += 1
		return ans


class Solution:

	def palindromeSubStrs(self, Str):
		arr = []
		count = 0
		for i in range(len(Str)):
			l = r = i
			while l >= 0 and r < len(Str) and (Str[l] == Str[r]):
				arr.append(Str[l:r + 1])
				count += 1
				l -= 1
				r += 1
			l = i
			r = i + 1
			while l >= 0 and r < len(Str) and (Str[l] == Str[r]):
				arr.append(Str[l:r + 1])
				count += 1
				l -= 1
				r += 1
		return len(set(arr))


class Solution:

	def palindromeSubStrs(self, s):
		res = 0
		dic = {}
		dic = set()
		for i in range(len(s)):
			(l, r) = (i, i)
			while l >= 0 and r < len(s) and (s[r] == s[l]):
				if s[l:r + 1] not in dic:
					res += 1
					dic.add(s[l:r + 1])
				l -= 1
				r += 1
			(l, r) = (i, i + 1)
			while l >= 0 and r < len(s) and (s[r] == s[l]):
				if s[l:r + 1] not in dic:
					res += 1
					dic.add(s[l:r + 1])
				l -= 1
				r += 1
		return res


class Solution:

	def palindromeSubStrs(self, str):
		l = len(str)
		ls = [0 for i in range(2 * l + 2)]
		a = '@#'
		for i in str:
			a += i
			a += '#'
		a += '@'
		s = set()
		for i in range(2, l * 2 + 2):
			while a[i - ls[i] - 1] == a[i + ls[i] + 1] and (a[i - ls[i] - 1] != '@' or a[i + ls[i] + 1] != '@'):
				ls[i] += 1
				if a[i] == '#' and ls[i] != 0:
					m = i // 2 - ls[i] // 2
					n = i // 2 + ls[i] // 2
					b = str[m:n]
					s.add(b)
				elif a[i] != '#' and ls[i] != 0:
					m = i // 2 - ls[i] // 2 - 1
					n = i // 2 + ls[i] // 2
					b = str[m:n]
					s.add(b)
				if a[i] != '#' and a[i] != '@' and (ls[i] != 0):
					s.add(a[i])
		if '' in s:
			s.remove('')
		return len(s)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		Str = input()
		solObj = Solution()
		print(solObj.palindromeSubStrs(Str))


class Solution:

	def palindromeSubStrs(self, s):
		res = set()
		for i in range(len(s)):
			l = i
			h = i
			while l >= 0 and h < len(s) and (s[l] == s[h]):
				res.add(s[l:h + 1])
				l -= 1
				h += 1
			l = i
			h = i + 1
			while l >= 0 and h < len(s) and (s[l] == s[h]):
				res.add(s[l:h + 1])
				l -= 1
				h += 1
		return len(res)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		Str = input()
		solObj = Solution()
		print(solObj.palindromeSubStrs(Str))


class Solution:

	def palindromeSubStrs(self, s):
		m = dict()
		n = len(s)
		R = [[0 for x in range(n + 1)] for x in range(2)]
		s = '@' + s + '#'
		for j in range(2):
			rp = 0
			R[j][0] = 0
			i = 1
			while i <= n:
				while s[i - rp - 1] == s[i + j + rp]:
					rp += 1
				R[j][i] = rp
				k = 1
				while R[j][i - k] != rp - k and k < rp:
					R[j][i + k] = min(R[j][i - k], rp - k)
					k += 1
				rp = max(rp - k, 0)
				i += k
		s = s[1:len(s) - 1]
		m[s[0]] = 1
		for i in range(1, n):
			for j in range(2):
				for rp in range(R[j][i], 0, -1):
					m[s[i - rp - 1:i - rp - 1 + 2 * rp + j]] = 1
			m[s[i]] = 1
		return str(len(m))
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		Str = input()
		solObj = Solution()
		print(solObj.palindromeSubStrs(Str))


class Solution:

	def palindromeSubStrs(self, Str):
		d = {}
		n = len(Str)
		for i in range(n):
			l = i
			r = i + 1
			p = i
			q = i
			while l >= 0 and r < n and (Str[l] == Str[r]):
				p = l
				q = r
				l -= 1
				r += 1
				s1 = Str[p:q + 1]
				if s1 not in d:
					d[s1] = 1
			s1 = Str[p:q + 1]
			if s1 not in d:
				d[s1] = 1
			l = i
			r = i
			p = i
			q = i
			while l >= 0 and r < n and (Str[l] == Str[r]):
				p = l
				q = r
				l -= 1
				r += 1
				s1 = Str[p:q + 1]
				if s1 not in d:
					d[s1] = 1
			s1 = Str[p:q + 1]
			if s1 not in d:
				d[s1] = 1
		return len(d)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		Str = input()
		solObj = Solution()
		print(solObj.palindromeSubStrs(Str))


class Solution:

	def palindromeSubStrs(self, s):
		(ans, p) = (set(s), len(s))
		for i in range(p):
			(a, b) = (i - 1, i + 1)
			while a >= 0 and b < p:
				if s[a] == s[b]:
					ans.add(s[a:b + 1])
				else:
					break
				a -= 1
				b += 1
			(a, b) = (i, i + 1)
			while a >= 0 and b < p:
				if s[a] == s[b]:
					ans.add(s[a:b + 1])
				else:
					break
				a -= 1
				b += 1
		return len(ans)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		Str = input()
		solObj = Solution()
		print(solObj.palindromeSubStrs(Str))


class Solution:

	def palindromeSubStrs(self, Str):
		res = 0
		charSet = set()
		for i in range(len(Str)):
			(l, r) = (i, i)
			while l >= 0 and r < len(Str) and (Str[l] == Str[r]):
				charSet.add(Str[l:r + 1])
				res += 1
				l -= 1
				r += 1
			(l, r) = (i, i + 1)
			while l >= 0 and r < len(Str) and (Str[l] == Str[r]):
				charSet.add(Str[l:r + 1])
				res += 1
				l -= 1
				r += 1
		return len(charSet)


class Solution:

	def palindromeSubStrs(self, Str):
		s = set()
		for i in range(len(Str)):
			x = y = i
			while x >= 0 and y < len(Str) and (Str[x] == Str[y]):
				t = Str[x:y + 1]
				if t:
					s.add(t)
				x -= 1
				y += 1
			x = i
			y = i + 1
			while x >= 0 and y < len(Str) and (Str[x] == Str[y]):
				t = Str[x:y + 1]
				if t:
					s.add(t)
				x -= 1
				y += 1
		return len(s)


class Solution:

	def palindromeSubStrs(self, Str):
		visited = []
		for i in range(len(Str)):
			start = i
			end = i
			while start >= 0 and end < len(Str) and (Str[start] == Str[end]):
				if Str[start:end + 1] not in visited:
					visited.append(Str[start:end + 1])
					start -= 1
					end += 1
				else:
					start -= 1
					end += 1
			start = i
			end = i + 1
			while start >= 0 and end < len(Str) and (Str[start] == Str[end]):
				if Str[start:end + 1] not in visited:
					visited.append(Str[start:end + 1])
					start -= 1
					end += 1
				else:
					start -= 1
					end += 1
		return len(visited)


class Solution:

	def palindromeSubStrs(self, s):
		n = len(s)
		result = set()
		for i in range(n):
			left = right = i
			while left >= 0 and right < n and (s[left] == s[right]):
				result.add(s[left:right + 1])
				left -= 1
				right += 1
			left = i
			right = i + 1
			while left >= 0 and right < n and (s[left] == s[right]):
				result.add(s[left:right + 1])
				left -= 1
				right += 1
		return len(result)


class Solution:

	def palindromeSubStrs(self, s):
		n = len(s)
		ss = set()
		for i in range(n - 1):
			left = i
			right = i + 1
			while left >= 0 and right < n:
				if s[left] == s[right]:
					ss.add(s[left:right + 1])
					left -= 1
					right += 1
				else:
					break
		for i in range(n):
			left = i - 1
			right = i + 1
			while left >= 0 and right < n:
				if s[left] == s[right]:
					ss.add(s[left:right + 1])
					left -= 1
					right += 1
				else:
					break
		for ele in s:
			ss.add(ele)
		return len(ss)


class Solution:

	def fetch_palindromes(self, s, left, right):
		result = []
		while left >= 0 and right < len(s) and (s[left] == s[right]):
			result.append(s[left:right + 1])
			left -= 1
			right += 1
		return result

	def palindromeSubStrs(self, Str):
		result = []
		for i in range(len(Str)):
			result.extend(self.fetch_palindromes(Str, i, i))
			result.extend(self.fetch_palindromes(Str, i, i + 1))
		return len(set(result))


class Solution:

	def palindromeSubStrs(self, S):
		res = ''
		output = set()
		for i in range(len(S)):
			(l, r) = (i, i)
			while l >= 0 and r < len(S) and (S[l] == S[r]):
				res = S[l:r + 1]
				output.add(res)
				l -= 1
				r += 1
			(l, r) = (i, i + 1)
			while l >= 0 and r < len(S) and (S[l] == S[r]):
				res = S[l:r + 1]
				output.add(res)
				l -= 1
				r += 1
		return len(output)


class Solution:

	def palindromeSubStrs(self, Str):
		s = Str
		start = 0
		st = set()
		for i in range(len(s)):
			st.add(s[i])
		for i in range(1, len(s)):
			l = i - 1
			r = i
			while l >= 0 and r < len(s) and (s[l] == s[r]):
				start = l
				st.add(s[start:r + 1])
				l -= 1
				r += 1
			l = i - 1
			r = i + 1
			while l >= 0 and r < len(s) and (s[l] == s[r]):
				start = l
				st.add(s[start:r + 1])
				l -= 1
				r += 1
		return len(st)


class Solution:

	def palindromeSubStrs(self, Str):
		res = set()
		for i in range(len(Str)):
			a = i
			b = i
			while a >= 0 and b < len(Str) and (Str[a] == Str[b]):
				res.add(Str[a:b + 1])
				a -= 1
				b += 1
			a = i
			b = i + 1
			while a >= 0 and b < len(Str) and (Str[a] == Str[b]):
				res.add(Str[a:b + 1])
				a -= 1
				b += 1
		return len(res)


class Solution:

	def palindromeSubStrs(self, s):
		mem = set()
		cnt = 0
		n = len(s)
		for i in range(n):
			(l, r) = (i, i)
			while l >= 0 and r < n and (s[l] == s[r]):
				if s[l:r + 1] not in mem:
					cnt += 1
					mem.add(s[l:r + 1])
				l -= 1
				r += 1
			(l, r) = (i, i + 1)
			while l >= 0 and r < n and (s[l] == s[r]):
				if s[l:r + 1] not in mem:
					cnt += 1
					mem.add(s[l:r + 1])
				l -= 1
				r += 1
		return cnt


class Solution:

	def palindromeSubStrs(self, Str):

		def countPalindrome(left, right):
			nonlocal unique_palindrome
			while left >= 0 and right < len(Str) and (Str[left] == Str[right]):
				unique_palindrome.add(Str[left:right + 1])
				left -= 1
				right += 1
		unique_palindrome = set()
		for i in range(len(Str)):
			countPalindrome(i, i)
			countPalindrome(i, i + 1)
		return len(unique_palindrome)


class Solution:

	def palindromeSubStrs(self, s):
		res = set()
		for i in range(len(s)):
			low = i
			high = i
			while low >= 0 and high < len(s) and (s[low] == s[high]):
				res.add(s[low:high + 1])
				low -= 1
				high += 1
			low = i
			high = i + 1
			while low >= 0 and high < len(s) and (s[low] == s[high]):
				res.add(s[low:high + 1])
				low -= 1
				high += 1
		return len(res)


class Solution:

	def palindromeSubStrs(self, Str):

		def find_palindromes_in_sub_string(input, j, k, visited):
			count = 0
			while j >= 0 and k < len(input):
				if input[j] != input[k]:
					break
				if input[j:k + 1] not in visited:
					visited[input[j:k + 1]] = True
					count += 1
				j -= 1
				k += 1
			return count
		count = -1
		visited = {}
		count = 0
		for i in range(0, len(Str)):
			count += find_palindromes_in_sub_string(Str, i - 1, i, visited)
			count += find_palindromes_in_sub_string(Str, i, i, visited)
		return count


class Solution:

	def palindromeSubStrs(self, Str):
		bag = set()
		for i in range(len(Str)):
			l = r = i
			bag.update(self.findPalindrome(Str, l, r))
			l = i
			r = i + 1
			bag.update(self.findPalindrome(Str, l, r))
		return len(bag)

	def findPalindrome(self, s, l, r):
		res = []
		while l >= 0 and r < len(s) and (s[l] == s[r]):
			res.append(s[l:r + 1])
			l -= 1
			r += 1
		return res


class Solution:

	def palindromeSubStrs(self, Str):
		dct = {}
		i = 0
		n = len(Str)
		while i < n:
			dct[Str[i]] = dct.get(Str, 0) + 1
			prev = i - 1
			next = i + 1
			while prev >= 0 and next < n:
				if Str[prev] == Str[next]:
					dct[Str[prev:next + 1]] = dct.get(Str[prev:next + 1], 0) + 1
					prev -= 1
					next += 1
				else:
					break
			prev1 = i
			next1 = i + 1
			while prev1 >= 0 and next1 < n:
				if Str[prev1] == Str[next1]:
					dct[Str[prev1:next1 + 1]] = dct.get(Str[prev1:next1 + 1], 0) + 1
					prev1 -= 1
					next1 += 1
				else:
					break
			i += 1
		return len(dct)


class Solution:

	def palindromeSubStrs(self, Str):
		substrings = set()
		substrings.union(set([ch for ch in Str]))
		for i in range(0, len(Str)):
			left = i
			right = i
			while left >= 0 and right <= len(Str) - 1 and (Str[left] == Str[right]):
				substrings.add(Str[left:right + 1])
				left -= 1
				right += 1
			left = i
			right = i + 1
			while left >= 0 and right <= len(Str) - 1 and (Str[left] == Str[right]):
				substrings.add(Str[left:right + 1])
				left -= 1
				right += 1
		return len(substrings)


class Solution:

	def find(self, Str, low, high, pal):
		while low >= 0 and high <= len(Str) - 1 and (Str[low] == Str[high]):
			pal.add(Str[low:high + 1])
			low = low - 1
			high = high + 1

	def palindromeSubStrs(self, Str):
		pal = set()
		for i in range(len(Str)):
			self.find(Str, i, i, pal)
			self.find(Str, i, i + 1, pal)
		return len(pal)


class Solution:

	def palindromeSubStrs(self, s):
		ans = set()

		def helper(i, j):
			c = 0
			while i >= 0 and j < len(s) and (s[i] == s[j]):
				ans.add(s[i:j + 1])
				i -= 1
				j += 1
		for i in range(len(s)):
			helper(i, i)
			helper(i, i + 1)
		return len(ans)


class Solution:

	def palindromeSubStrs(self, Str):
		lst = []
		for index in range(len(Str)):
			findPali(index, index, Str, lst)
			findPali(index, index + 1, Str, lst)
		return len(set(lst))

def findPali(start, end, str, lst):
	while start >= 0 and end < len(str) and (str[start] == str[end]):
		start -= 1
		end += 1
		lst.append(str[start + 1:end])