LC647 - Palindromic Substrings

Problem

Given a string s, return the number of palindromic substrings in it. A string is a palindrome when it reads the same backward as forward. A substring is a contiguous sequence of characters within the string.

Example

Input: s = "abc"

Output: 3

Explanation: Three palindromic strings: "a", "b", "c"

Solution

Expand Palindrome from Centre

We take the solution from LC005 and build upon it. We check whether or not a substring is a palindrome from its center, and iterate across the characters in the string array, expanding outwards from each character to check whether or not it is a palindrome. For each expansion, we add one count to the number of palindromic substrings. Time complexity of this approach will be $O(n^2)$, and we don't use extra space so space complexity is $O(1)$.

def expand(self, s: str, i, j):
	lbound = i
	rbound = j
	subcount = 0

	# expand if bounds don't reach end	
	while lbound >= 0 and rbound < len(s) and s[lbound] == s[rbound]:
	lbound -= 1
	rbound += 1
	subcount += 1
	
	# return number of palindromes found
	return subcount
	
def countSubstrings(self, s: str) -> int:
	odd = 0
	even = 0
	
	for i in range(len(s)):
		# expand for odd length palindromes
		odd += self.expand(s, i, i)
		# expand for even length palindromes
		even += self.expand(s, i, i + 1)
	
	return odd + even