# AC Javascript version

• I don't know why but a plain O(n^2) algorithm gets TLE so I wrote a theoretically O(n^2) but on average nearly O(n) code. Key idea is that

1. X is palindrome <==> aXa is also palindrome.
2. X is made of only one character c <==> Xc is also a palindrome made of only c.
3. any single character itself is a palindrome string of length=1.

So we can get new possible palindrome ending at i based on palindrome ending at i-1.

Coffeescript code:

``````longestPalindrome = (s) ->
bestOffset = 0
bestLength = 1

onlyOneChar =
prevLength: 1
prevSingleCharacter: true

prevPossibilities = [onlyOneChar]

for i in [1...s.length]
allPossibilities = [onlyOneChar]
for {prevLength, prevSingleCharacter} in prevPossibilities
# the start index of the previous palindrome
prevStart = i-prevLength
len = 0
if prevStart >= 1 and s[i] is s[prevStart-1]
# constructing "a{prev}a" type of palindrome
len = prevLength + 2
singleCharacter = prevSingleCharacter and s[i] is s[i-1]
else if prevStart >= 0 and s[i] is s[prevStart] and prevSingleCharacter
# constructing "{aaaaa}a" type of palindrome
len = prevLength + 1
singleCharacter = true
if len > 0
if len > bestLength
bestLength = len
bestOffset = i
allPossibilities.push
prevLength: len
prevSingleCharacter: singleCharacter
prevPossibilities = allPossibilities

return s.substr(bestOffset-bestLength+1, bestLength)``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.