Palindromic Substrings

Patrick Leaton
Published: May 11, 2021, 4:31 a.m.
Problem Description

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.

 

The description was taken from https://leetcode.com/problems/palindromic-substrings/.

Problem Solution

#O(N^2) Time, O(1) Space
class Solution:
    def countSubstrings(self, s: str) -> int:
        count = 0
        for i in range(0, len(s)):
            count += self.helper(s, i, i)
            count += self.helper(s, i, i+1)
        return count
   
    def helper(self, s: str, left: int , right: int) -> int:
        count = 0
        while left >= 0 and right < len(s):
            if s[left] == s[right]:
                left -= 1
                right += 1
                count += 1
            else:
                break
        return count

Problem Explanation

The problem can be solved with a solution that is very similar to the Longest Palindromic Substring problem.

Both involve stepping through the input string and calling a helper function on each character that checks for palindromes while expanding two pointers outward.

The difference between the two is we are looking for the total amount of palindromes within the input string instead of the longest palindrome.

Let's start by creating the helper function first.

The function will take a string, a left pointer, and a right pointer.  It will return the count as an integer.

    def helper(self, s: str, left: int , right: int) -> int:

 

We will initialize the count to zero.

        count = 0

 

Next, we will create a loop that will run while the left pointer hasn't gone past the first letter of the string and while the right pointer hasn't gone past the last.

        while left >= 0 and right < len(s):

 

During each iteration, if the letter at the left pointer matches the letter at the right pointer, then we have a valid palindrome so we will move the pointers outward and increment the count by one.

            if s[left] == s[right]:
                left -= 1
                right += 1
                count += 1

 

If there is a mismatch we will break out of the loop.

            else:
                break

 

Once we have broken from the loop, we will return the count of palindromes that we were able to count.

        return count

 

Let's take the input of "abcba" for example.

We would return three palindromes for this function if the function was called on "c".  

We would have "c" + "bcb" + "abcba".

Now let's move back up to the countSubstrings function.

We will initialize our count to zero.

        count = 0

 

Next, we will step through the string.  

During each step, we will call the helper function on our current character.  

There are two possibilities for the center of a palindrome here. 

Either a palindrome has an odd-numbered length and the center is one letter like "aba", or a palindrome has an even-numbered length and the center is two letters like "abba".  

To handle both cases, we will call the function while passing the current index as the left and right pointers, then we will also call it again while passing the current index and the next index as the left and right pointers.  We will increment our count by the returned values.

            count += self.helper(s, i, i)
            count += self.helper(s, i, i+1)

 

Once we have stepped through the entire string and have collected the count of each valid palindrome, we will return the count.

        return count