LeetCode 05 with Manacher's algorithm

Question

I finished LeetCode 05 with simplified (for ease of implementation) Manacher's algorithm. IMHO it should keeps \$\mathcal{O}(n)\$ time and space complexity. However, LeetCode's benchmark ranked my solution as worst 5% and 30%. What causes such poor performance (time and space)? Can anybody help me diagnose where it went wrong?

Description:

Given a string s, return the longest palindromic substring in s.

Example:

Input: s = "babad" 
Output: "bab" 
Note: "aba" is also a valid answer. 

Code:

data class LimitInfo(var center: Int, var rightMost: Int)
class Solution {
 fun longestPalindrome(s: String): String {
 val newS = s.fold("#") { acc, c -> "$acc$c#" }
 val radii = MutableList(newS.length) { 0 }
 val limitInfo = LimitInfo(0, 0)
 fun symRadius(center: Int, checkedRadius: Int): Int {
 var radius = checkedRadius + 1
 while (newS.getOrNull(center - radius)?.equals(newS.getOrNull(center + radius)) == true) radius += 1
 return radius - 1
 }
 newS.indices.forEach { center ->
 val space = limitInfo.rightMost - center
 val checkedRadius = when {
 space < 0 -> 0
 else -> minOf(radii[limitInfo.center * 2 - center], space)
 }
 val radius = symRadius(center, checkedRadius)
 radii[center] = radius
 if (center + radius > limitInfo.rightMost) {
 limitInfo.rightMost = center + radius
 limitInfo.center = center
 }
 }
 val res = radii.withIndex().maxBy { it.value }!!.let { (loc, radius) ->
 newS.slice(loc - radius..loc + radius)
 }.filterIndexed { index, _ -> index % 2 == 1 }
 return res
 }
}

Answer 1

I think the way you're folding it to create newS is \$\mathcal{O}(n^2)\$. Try instead:

val newS = buildString { 
 append('#')
 s.forEach { append(it).append('#') } 
}

Also consider that most respondents are probably inputting \$\mathcal{O}(n)\$ solutions, so smaller optimizations that don't affect big O might make a big difference in your percentile. For example, using an IntArray instead of MutableList, manually iterating instead of boxing with withIndex(), eliminating the unnecessary intermediate LimitInfo class, checking indices and using get() instead of getOrNull(), etc.

Answer 2

At least in the worst case you can get \$\mathcal{O}(n^2)\$. For some strings (like 'aaaaaaaaa') any substring is going to be symmetric. That's why symRadius function may take \$\mathcal{O}(n)\$. So in worst case symRadius is called with \$\mathcal{O}(n)\$ complexity for all \$n\$ chars (which should lead to \$\mathcal{O}(n^2)\$ in total).

• llama: But the biggest performance issue indeed should be related to string concatenation in the fold. As already mentioned @Tenfour04.
• Turmiht Lynn: In my logic, symRadius accepts checkedRadius as starting point for further checks. In your example, except for first several 'a', symRadius will get pretty big initial checkedRadius from radii, since preventing square complexity. is it right? BTW, I suppose it as linear since rightMost keeps going rightward, no very strict but intuitive inference.