I'm trying a leetcode challenge and am struggling to pass the challenge due to the speed of my code:

class Solution {
    fun longestPalindrome(s: String): String {
        var longestPal = ""
        var substring = ""
        for (i in 0..s.length) {
            for (j in i   1..s.length) {
                substring = s.substring(i, j)
                if (substring == substring.reversed() && substring.length > longestPal.length) {
                    longestPal = substring
                }
            }
        }
        return longestPal
    }
}

I'm a newb and not familiar with Big O notation. I imagine if I could use just one loop I would be able to speed this code up significantly but am not sure how I would go about this.

CodePudding user response：

(Not saying this is the best approach, but that is a start)

Palindromes can only be found between two same letters. So one idea is to go through the string once, and keep track of letter indexes. When you encounter a letter you already saw before, and the difference in indexes is longer than the current longest palindrome, you check for a palindrome:

fun longestPal(s: String): String {
  val letters = mutableMapOf<Char, MutableList<Int>>()
  var longest = ""
  s.indices.forEach { index ->
    val indicesForCurrentChar = letters[s[index]] ?: mutableListOf()
    for (i in indicesForCurrentChar) {
      if ((index - i) < longest.length) break // (1) won't be the longest anyway
      val sub = s.substring(i, index   1)
      if (sub == sub.reversed()) longest = sub

    }
    indicesForCurrentChar.add(index)
    letters[s[index]] = indicesForCurrentChar
  }
  return longest
}

What is costly here is the palindrome check itself (sub == sub.reversed). But the check in (1) should contain it (think of a string which is the repetition of the same letter).

I would be curious to know what other suggest online.

CodePudding user response：

Your code runs in O(n^3) time, a loop within a loop within a loop, because that reversed() call iterates up to the size of the input string. You can look up Manacher's algorithm for an explanation of how to do it in linear time (O(n)), no nested iteration at all.