# Scala algorithm: Find the longest palindrome within a string

Published

## Algorithm goal

The palindrome in String `XYZdZe`

is **XdZdZdX****XdZdZdX**. Compute the longest sub-string palindrome in a given string.

Note: there are many solutions to this problem that may be wrong.

## Test cases in Scala

```
assert(longestPalindrome("X") == "X".length)
assert(longestPalindrome("XYZdZ") == "ZdZ".length)
assert(longestPalindrome("XYZdZeX") == "ZdZ".length)
assert(longestPalindrome("XYZdZeXdZdZd") == "dZdZd".length)
assert(longestPalindrome("XYZdZeXdZdZdX") == "XdZdZdX".length)
assert(longestPalindrome("XYZdZeXdZZdX") == "XdZZdX".length)
assert(longestPalindromeBrute("XYZdZ") == "ZdZ")
assert(longestPalindromeBrute("XYZdZeX") == "ZdZ")
assert(longestPalindromeBrute("XYZdZeXdZdZd") == "dZdZd")
assert(longestPalindromeBrute("XYZdZeXdZdZdX") == "XdZdZdX")
assert(longestPalindromeBrute("XYZdZeXdZZdX") == "XdZZdX")
```

## Algorithm in Scala

43 lines of Scala (compatible versions 2.13 & 3.0).

## Explanation

We use a dynamic programming style solution.

Notice that if 'aBa' is a palindrome, then '?aBa!' is also a palindrome if '?' and '!' are equal. (this is Â© from www.scala-algorithms.com)

By defining Palindrome(i, j) to be 'true' if there is a palindrome starting at i, and ending at j, we have the following:

- Palindrome(i, i) = true
- Palindrome(i, i + 1) = char at i == char at i + 1
- Palindrome(i, j) = Palindrome (i + 1, j - 1) && char at i == char at i + 1

## Scala concepts & Hints

### Drop, Take, dropRight, takeRight

Scala's `drop` and `take` methods typically remove or select `n` items from a collection.

### For-comprehension

The for-comprehension is highly important syntatic enhancement in functional programming languages.

### Range

The

`(1 to n)`

syntax produces a "Range" which is a representation of a sequence of numbers.