0647: Palindromic Substrings

Problem Statement

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 1:

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Constraints:

  • 1 <= s.length <= 1000
  • s consists of lowercase English letters.

Code Solution

class Solution:
    def countSubstrings(self, s):
        N = len(s)
        count = 0
        # odd strings:
        for ix in range(N):
            lx = ix
            rx = ix
            while lx >= 0 and rx <= N - 1 and s[lx] == s[rx]:
                lx = lx - 1
                rx = rx + 1
                count = count + 1
        # even strings:
        for ix in range(N - 1):
            lx = ix
            rx = ix + 1
            while lx >= 0 and rx <= N - 1 and s[lx] == s[rx]:
                lx = lx - 1
                rx = rx + 1
                count = count + 1
        return count