> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/ecs122a-algorithm-design-lecture-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/ecs122a-algorithm-design-lecture-notes/string-algorithms/suffix-trees/applications/longest-palindromic-substring.md).

# Longest Palindromic Substring

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

**Example:**

```
Input:
 "babad"


Output:
 "bab"


Note:
 "aba" is also a valid answer.
```

**Example:**

```
Input:
 "cbbd"


Output:
 "bb"
```

**Solution**

Assume the string S = "banana". Begin by building the suffix tree, for S + R, where R is the reverse of S.

```
S = b a n a n a $ a n a n a b #
I = 1 2 3 4 5 6 7 8 9 0 1 2 3 4
```

![](https://4248470099-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LoJHphnGN5n2jKpXzYL%2F-LoJHqLx4tZP9WYw_RQZ%2F-LoJI4g3O0zNLQtH1pCY%2FSF_palindrome.png?generation=1568003612746189\&alt=media)

Finally, return the path label along the LCS.

![](https://4248470099-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LoJHphnGN5n2jKpXzYL%2F-LoJHqLx4tZP9WYw_RQZ%2F-LoJI4g6luFWuHyhKG5h%2FSF_palindrome_sol.png?generation=1568003612711828\&alt=media)

**Why this works**

This works exactly for the same reasons justified in the previous application. Since a palindrome is the same both backwards and forwards, its common shared occurrence will remain the same when the pattern is reversed. Then the properties of the LCS remain the same as before.