Skip to content

String Manacher Algorithm

Table of Contents

5. Longest Palindromic Substring

class longestPalindrome:
    """Return the longest palindromic substring in s."""

    @staticmethod
    def dp(s: str) -> str:
        n = len(s)
        if n <= 1:
            return s

        start, maxLen = 0, 1

        # Init
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 1

        # update
        for j in range(1, n):
            for i in range(j):
                if s[i] == s[j]:
                    if j - i <= 2:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i + 1][j - 1]

                    if dp[i][j] and j - i + 1 > maxLen:
                        maxLen = j - i + 1
                        start = i

        return s[start : start + maxLen]

    @staticmethod
    def expand_around_center(s: str) -> str:
        def expand(left, right):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return right - left - 1

        if len(s) <= 1:
            return s

        start, end = 0, 0
        for i in range(len(s)):
            odd = expand(i, i)
            even = expand(i, i + 1)

            maxLen = max(odd, even)
            if maxLen > end - start:
                start = i - (maxLen - 1) // 2
                end = i + maxLen // 2

        return s[start : end + 1]


if __name__ == "__main__":
    s = "babad"
    assert longestPalindrome.dp(s) in ["bab", "aba"]
    assert longestPalindrome.expand_around_center(s) in ["bab", "aba"]

647. Palindromic Substrings

"""
-   Return the number of palindromic substrings in `s`.
-   Bottom-up DP table

|  dp   |  a  |  b  |  b  |  a  |  e  |
| :---: | :-: | :-: | :-: | :-: | :-: |
| **a** |  1  |  0  |  0  |  1  |  0  |
| **b** |  0  |  1  |  1  |  0  |  0  |
| **b** |  0  |  0  |  1  |  0  |  0  |
| **a** |  0  |  0  |  0  |  1  |  0  |
| **e** |  0  |  0  |  0  |  0  |  1  |
"""


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

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

    return res


print(countSubstrings("abbae"))  # 7

214. Shortest Palindrome

  • LeetCode | 力扣

  • Tags: String, Rolling Hash, String Matching, Hash Function

from leetpattern.utils import LPS


# KMP
def shortestPalindrome(s: str) -> str:
    if not s:
        return s

    new = s + "#" + s[::-1]
    lps = LPS(new)

    add_len = len(s) - lps[-1]

    return s[::-1][:add_len] + s


print(shortestPalindrome("aacecaaa"))  # aaacecaaa

3327. Check if DFS Strings Are Palindromes

  • LeetCode | 力扣

  • Tags: Array, Hash Table, String, Tree, Depth First Search, Hash Function

1745. Palindrome Partitioning IV

# DP
def checkPartitioning(s: str) -> bool:
    def palidrome_partition(s, k):
        n = len(s)
        min_change = [[0] * n for _ in range(n)]
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                min_change[i][j] = min_change[i + 1][j - 1] + (1 if s[i] != s[j] else 0)

        dp = min_change[0]

        for i in range(1, k):
            for right in range(n - k + i, i - 1, -1):
                dp[right] = min(
                    dp[left - 1] + min_change[left][right] for left in range(i, right + 1)
                )

        return dp[-1]

    return palidrome_partition(s, 3) == 0


s = "abcbdd"
print(checkPartitioning(s))  # True

1960. Maximum Product of the Length of Two Palindromic Substrings