Count number of palindromic substrings (non-empty) of a string

PalindromicSubstrings.scala

/**
  * Dumb O(n^3) version: Check if all n^2 substrings are palindromes
  */
def countPalindromes3(s: String): Int =
  (1 to s.length).flatMap(s.sliding).count(t => t.reverse == t)

/***********************************************************************/
/**
 * O(n^2) solution - count how many (odd and even) palindromes are centered at index i by expanding left and right
 */
def countPalindromes2(s: String): Int = {

  def count(left: Int, right: Int): Int =
    if (0 <= left && right < s.length && s(left) == s(right)) 1 + count(left - 1, right + 1) else 0
  
  def even(idx: Int) = count(left = idx, right = idx + 1)
  def odd(idx: Int) = count(left = idx, right= idx)

  s.indices.map(idx => odd(idx) + even(idx)).sum
}

/***********************************************************************/

/**
  * O(n) algo - Manacher's algorithm
  * TODO: https://github.com/int8/Manacher-Algorithm-in-Scala/blob/master/src/main/scala/solvers/FunctionalLinearImmutable.scala
  */
def countPalindromes1(s: String): Int = {
  ???
}