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).