Palindromic Substring

This question comes in varieties:

• Longest palindromic substring
• All palindromic substring
• Palindromic decomposition

alg. palindromic substring search.¹

• Double Loop, on $\text{index}\times \text{substr. length}$: $O(n^2)$
• DP: $O(n^2)$
• Manacher’s algorithm²

alg. Smallest Palindromic Decomposition. Homework Link

1. run substring search (by any of above)
2. run DP to get smallest decomposition

alg. Palindromic Subsequence search.³ Complicated much more by the fact that it’s a subsequence.

• A variant of Dynamic Programming
• Idea 1: run for every char
• Idea 2: ¶bccab, we see $b,b$ is a subseq. We then consider the inner b + {inner} + b and count the inner subseq.

Footnotes §

1. Longest Palindromic Substring, CS330 ↩

2. Longest Palindromic Substring Manacher’s Algorithm - YouTube ↩

3. Count Different Palindromic Subsequences - LeetCode ↩