# Coding Patterns: Palindromes (DP)

In **Coding Patterns** series, we will try to *recognize* common patterns *underlying* behind each algorithm question, using real examples from Leetcode.

Previous posts were about Sliding Window, Two Pointers, Fast & Slow Pointers, Merge Intervals, Cyclic Sort, In-place Reversal of a Linked List, Breadth First Search (BFS), Depth First Search (DFS), Two Heaps, Subsets, Modified Binary Search, Top K Numbers, K-way Merge, 0/1 Knapsack, Topological Sort, Bitwise XOR and Staircase patterns and today, we will introduce Palindromes pattern which is very useful to solve Dynamic Programming problems involving **palindromes** and **palindromic** *strings*, *substrings*, *subsequences* etc.

If you need to refresh your knowledge of Dynamic Programming, you may want to check it before diving into more advanced problems.

## Problem: Longest Palindromic Subsequence

**LeetCode 516 - Longest Palindromic Subsequence** [*medium*]

Given a string **s**, find the longest palindromic subsequence’s length in **s**. You may assume that the *maximum length* of **s** is **1000**.

**Example 1:**

**Input:** “bbbab”

**Output:** 4

One possible longest palindromic subsequence is “bbbb”.

**Example 2:**

**Input:** “cbbd”

**Output:** 2

One possible longest palindromic subsequence is “bb”.

### Brute Force Solution

A

palindromeis aword,number,phrase, or other sequence of characters whichreads the same backward as forward, such asmadam,racecar, or the number10801.Sentence-length palindromes may be written when allowances are made for adjustments to capital letters, punctuation, and word dividers, such as “

A man, a plan, a canal, Panama!”, “Was it a car or a cat I saw?” etc.^{1}

As a **brute force** solution, we can try all *subsequences* of the given *sequence*. Starting from the beginning and the end of the sequence;

- if the elements at the beginning and the end are the same, we can increment the counter by
**2**and make a recursive call to remaining subsequences - we will skip one element either from the beginning or from the end o make two recursive calls for the remaining subsequence

If the **first option** applies then it will give us the length of *Longest Palindromic Substring ( LPS)*.

Otherwise, the length of *Longest Palindromic Substring ( LPS)* will be the maximum number returned by the

*two*recursive calls from

**the second option**.

```
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
return self.longestPalindromeSubseq_recursive(s, 0, len(s) - 1)
def longestPalindromeSubseq_recursive(self, s, start, end):
if start > end:
return 0
# every sequence with one element is a palindrome of length 1
if start == end:
return 1
# case 1: elements at the beginning and the end are the same
if s[start] == s[end]:
return 2 + self.longestPalindromeSubseq_recursive(s, start + 1, end - 1)
# case 2: skip one element either from the beginning or the end
subseq1 = self.longestPalindromeSubseq_recursive(s, start + 1, end)
subseq2 = self.longestPalindromeSubseq_recursive(s, start, end - 1)
return max(subseq1, subseq2)
```

**Time Complexity**: **O(2 ^{N})** because we are making

**2**recursive calls in the same function.

**Space Complexity**: **O(N)** which is used to store the recursion stack.

### Top-down Dynamic Programming with Memoization

`start`

and `end`

are two changing values of our recursive function in the Brute Force Solution. So, we can store the results of all subsequences in a two-dimensional array to *memoize* them.

```
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
memo = [[-1 for _ in range(len(s))] for _ in range(len(s))]
return self.longestPalindromeSubseq_recursive(memo, s, 0, len(s) - 1)
def longestPalindromeSubseq_recursive(self, memo, s, start, end):
if start > end:
return 0
# every sequence with one element is a palindrome of length 1
if start == end:
return 1
if memo[start][end] == -1:
# case 1: elements at the beginning and the end are the same
if s[start] == s[end]:
memo[start][end] = 2 + self.longestPalindromeSubseq_recursive(memo, s, start + 1, end - 1)
else:
# case 2: skip one element either from the beginning or the end
subseq1 = self.longestPalindromeSubseq_recursive(memo, s, start + 1, end)
subseq2 = self.longestPalindromeSubseq_recursive(memo, s, start, end - 1)
memo[start][end] = max(subseq1, subseq2)
return memo[start][end]
```

**Time Complexity**: **O(N ^{2})** because memoization array,

`memo[len(s)][len(s)]`

. We will not have more than **N*N**subsequences.

**Space Complexity**: **O(N ^{2} + N)** ==

**O(N**because we used

^{2})**N**for memoization array and

^{2}**N**for recursive stack.

### Bottom-up Dynamic Programming with Tabulation

We can build our two-dimensional memoization array in a bottom-up fashion, adding one element at a time.

- if the element at the
`start`

and the`end`

is matching, the length of*Longest Palindromic Substring (*is 2 plus the length of**LPS**)**LPS**till`start+1`

and`end-1`

. - if the element at the
`start`

does**not**match the element at the`end`

, we will take the`max`

of**LPS**by either skipping the element at`start`

or`end`

So the overall algorith will be;

```
if s[start] == s[end]:
memo[start][end] = 2 + memo[start + 1][end - 1]
else:
memo[start][end] = max(memo[start + 1][end], memo[start][end - 1])
```

and the solution;

```
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
memo = [[0 for _ in range(len(s))] for _ in range(len(s))]
# every sequence with one element is a palindrome of length 1
for i in range(len(s)):
memo[i][i] = 1
for start in range(len(s) - 1, -1, -1):
for end in range(start + 1, len(s)):
# case 1: elements at the beginning and the end are the same
if s[start] == s[end]:
memo[start][end] = 2 + memo[start + 1][end - 1]
else: # case 2: skip one element either from the beginning or the end
memo[start][end] = max(memo[start + 1][end], memo[start][end - 1])
return memo[0][len(s) - 1]
```

**Time Complexity**: **O(N ^{2})**

**Space Complexity**: **O(N ^{2})** where

**N**is the input sequence.

## How to identify?

Palindromes pattern is very useful to solve Dynamic Programming problems involving **palindromes** and **palindromic** *strings*, *substrings*, *subsequences* etc.

## Similar LeetCode Problems

- LeetCode 5 - Longest Palindromic Substring [
*medium*] - LeetCode 131 - Palindrome Partitioning [
*medium*] - LeetCode 647 - Palindromic Substrings [
*medium*] - LeetCode 1216 - Valid Palindrome III [
*hard*] [*premium*]

## References

- Wikipedia,
*Palindrome*