Palindromic Substrings

Problem

https://leetcode.com/problems/palindromic-substrings/

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.

Pattern

Two Pointers, String, Dynamic Programming

Approaches

Expand From Center

Code

def countSubstrings(s: str) -> int:
    substrs = 0

    for i in range(len(s)):
        for j in [1, 2]:
            left = i
            right = i + j

            while (
                0 <= left < right <= len(s)
                and s[left:right] == s[left:right][::-1]
            ):
                substrs += 1
                left -= 1
                right += 1

    return substrs

Test

>>> from palindromic_substrings__expand_from_center import countSubstrings
>>> countSubstrings("abc")
3
>>> countSubstrings("aaa")
6

palindromic_substrings__expand_from_center.countSubstrings(s: str) → int