Palindromic Substrings

Problem Statement

Given a string s, return the number of substrings within s that are palindromes.

A palindrome is a string that reads the same forward and backward.

Example 1:

Input: s = "abc"
Output: 3

Explanation: “a”, “b”, “c”.

Example 2:

Input: s = "aaa"
Output: 6

Explanation: “a”, “a”, “a”, “aa”, “aa”, “aaa”. Note that different substrings are counted as different palindromes even if the string contents are the same.

Constraints:

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

You should aim for a solution as good or better than O(n^2) time and O(1) space, where n is the length of the given string.

Recommended Time and Space Complexity

You should aim for a solution as good or better than O(n^2) time and O(1) space, where n is the length of the given string.

Hint 1

A brute-force solution would be to check if every substring is a palindrome and return the total number of palindromic substrings. This would be an O(n^3) time solution. Can you think of a better way? Perhaps you should consider thinking in terms of the center of a palindrome.

Hint 2

Iterate over the string with index i and treat the current character as the center. For this character, try to extend outward to the left and right simultaneously, but only if both characters are equal. At each iteration, we increment the count of palindromes. How would you implement this? Can you consider both cases: even-length and odd-length palindromes?

Hint 3

Initialize a variable res to track the count of palindromes. At each index, create an odd-length palindrome starting at that index extending outward from both its left and right indices, i.e., i - 1 and i + 1. How can you find the even-length palindrome for this index?

Hint 4

For an even-length palindrome, consider expanding from indices i and i + 1. This two-pointer approach, extending from the center of the palindrome, will help find all palindromic substrings in the given string and return its count.

Solution

Brute Force

def count_substrings(s: str) -> int:
    res = 0

    for i in range(len(s)):
        for j in range(i, len(s)):
            l, r = i, j
            while l < r and s[l] == s[r]:
                l += 1
                r -= 1
            res += (l >= r)

    return res

Time complexity: O(n^3) Space complexity: O(1)

Dynamic Programming

def count_substrings(s: str) -> int:
    n, res = len(s), 0
    dp = [[False] * n for _ in range(n)]

    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            if s[i] == s[j] and (j - i <= 2 or dp[i + 1][j - 1]):
                dp[i][j] = True
                res += 1

    return res

Time complexity: O(n^2) Space complexity: O(n^2)

Two Pointers

def count_substrings(s: str) -> int:
    res = 0

    for i in range(len(s)):
        # odd length
        l, r = i, i
        while l >= 0 and r < len(s) and s[l] == s[r]:
            res += 1
            l -= 1
            r += 1

        # even length
        l, r = i, i + 1
        while l >= 0 and r < len(s) and s[l] == s[r]:
            res += 1
            l -= 1
            r += 1

    return res

Time complexity: O(n^2) Space complexity: O(1)

Two Pointers (Optimal)

def count_substrings(s: str) -> int:
    res = 0

    for i in range(len(s)):
        res += count_palindromes(s, i, i)
        res += count_palindromes(s, i, i + 1)
    return res

def count_palindromes(s, l, r):
    res = 0
    while l >= 0 and r < len(s) and s[l] == s[r]:
        res += 1
        l -= 1
        r += 1
    return res

Time complexity: O(n^2) Space complexity: O(1)

Manacher’s Algorithm

def count_substrings(s: str) -> int:

    def manacher(s):
        t = '#' + '#'.join(s) + '#'
        n = len(t)
        p = [0] * n
        l, r = 0, 0
        for i in range(n):
            p[i] = min(r - i, p[l + (r - i)]) if i < r else 0
            while (i + p[i] + 1 < n and i - p[i] - 1 >= 0
                   and t[i + p[i] + 1] == t[i - p[i] - 1]):
                p[i] += 1
            if i + p[i] > r:
                l, r = i - p[i], i + p[i]
        return p

    p = manacher(s)
    res = 0
    for i in p:
        res += (i + 1) // 2
    return res

Time complexity: O(n) Space complexity: O(n)