# Longest Palindrome Subsequence

This is a variance of largest common subsequnceproblem

A palindrome is a nonempty string over some alphabet that reads the same forward and backward. Examples of palindromes are all strings of length 1, `civic`

, `racecar`

, and `aibohphobia`

(fear of palindromes). Give an efficient algorithm to find the longest palindrome that is a subsequence of a given input string. For example, given the input `character`

, your algorithm should return `carac`

. What is the running time of your algorithm?

```
fun largestPalindrome(x: String): String {
val y = x.reversed()
val dp = Array(x.length + 1) { IntArray(y.length + 1) { 0 } }
for (i in x.indices) {
for (j in y.indices) {
if (x[i] == y[j]) {
dp[i + 1][j + 1] = dp[i][j] + 1
} else {
dp[i + 1][j + 1] = maxOf(dp[i][j + 1], dp[i + 1][j])
}
}
}
var i = dp.lastIndex
var j = i
val sb = StringBuilder()
while (dp[i][j] > 0) {
when {
dp[i][j] == dp[i - 1][j] -> i--
dp[i][j] == dp[i][j - 1] -> j--
else -> {
i--
j--
sb.append(x[i])
}
}
}
return sb.toString()
}
```