Skip to content

DP Other Interval DP

Table of Contents

5. Longest Palindromic Substring

  • LeetCode | LeetCode CH (Medium)

  • Tags: two pointers, string, dynamic programming

  • Return the longest palindromic substring in s.
5. Longest Palindromic Substring - Python Solution
# DP - Interval
def longestPalindromeDP(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

    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]


# Expand Around Center
def longestPalindromeCenter(s: str) -> str:
    def expand_around_center(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)):
        len1 = expand_around_center(i, i)  # odd
        len2 = expand_around_center(i, i + 1)  # even

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

    return s[start : end + 1]


s = "babad"
print(longestPalindromeDP(s))  # "bab"
print(longestPalindromeCenter(s))  # "aba"

647. Palindromic Substrings

  • LeetCode | LeetCode CH (Medium)

  • Tags: two pointers, string, dynamic programming

  • 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
647. Palindromic Substrings - Python Solution
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

3040. Maximum Number of Operations With the Same Score II

375. Guess Number Higher or Lower II

1130. Minimum Cost Tree From Leaf Values

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, dynamic programming, stack, greedy, monotonic stack

96. Unique Binary Search Trees

  • LeetCode | LeetCode CH (Medium)

  • Tags: math, dynamic programming, tree, binary search tree, binary tree

1770. Maximum Score from Performing Multiplication Operations

1547. Minimum Cost to Cut a Stick

1039. Minimum Score Triangulation of Polygon

1000. Minimum Cost to Merge Stones

2019. The Score of Students Solving Math Expression

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, math, string, dynamic programming, stack, memoization

3277. Maximum XOR Score Subarray Queries

87. Scramble String

312. Burst Balloons

664. Strange Printer

546. Remove Boxes

471. Encode String with Shortest Length

3018. Maximum Number of Removal Queries That Can Be Processed I

Comments