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

Explanation

A palindrome mirrors around its center. Thus, we can find a palindromatic substring by starting from a center and expanding outwards as long as the characters on both sides are equal. For each character in the string, we consider it as a center of a palindrome and expand outwards. This covers odd lengthed palindromes. For even length palindromes, we consider centers of two consecutive characters.

Code

def countSubstrings(s: str) -> int:
    """Given a string ``s``, count the number of palindromatic substrings."""
    substrs = 0

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

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

    return substrs

Test

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

Complexity

\(n\) is the number of characters in s

Measure	Complexity	Notes
Time	\(O(n^2)\)	worst case every character is the center of a palindrome and we expand to the whole string (happens when the string is all the same character)
Auxiliary Space	\(O(1)\)

palindromic_substrings__expand_from_center.countSubstrings(s: str) → int

Given a string s, count the number of palindromatic substrings.