Palindromes.scala

import Function.const
import scala.annotation.tailrec
import scala.collection.SortedMap

object Palindrome {
  case class Palindrome(s: String, startIdx: Int)
  case class PalKey(index: Int, length: Int)
  type PalIndex = SortedMap[PalKey, Int]

  object Palindrome {
    def apply(s: String, palKey: PalKey): Palindrome = {
      val evenOffset = if (palKey.length % 2 == 0) 1 else 0
      val start = palKey.index - palKey.length / 2 + evenOffset
      val end = palKey.index + palKey.length / 2
      Palindrome(s.substring(start, end + 1), start)
    }

  }

  implicit val PalKeyOrdering = new Ordering[PalKey] {
    override def compare(x: PalKey, y: PalKey) =
      if (x.length == y.length) y.index.compare(x.index)
      else y.length.compare(x.length)
  }


  def countMatchingChars(s: String)(aI: Int, bI: Int): Int = {
    def inBound(i: Int) = i >= 0 && i < s.length
    if (!inBound(aI) || !inBound(bI)) {
      0
    }
    else if (s.substring(aI, aI + 1) == s.substring(bI, bI + 1)) {
      2 + countMatchingChars(s)(aI - 1, bI + 1)
    } else {
      0
    }
  }

  def longestPalindromes(s: String, n: Int): List[Palindrome] = {
    val f = countMatchingChars(s) _
    val index = Vector.range(0, s.length).foldLeft(SortedMap.empty[PalKey, Int]) { case (m, i) =>
      if (i + 1 < s.length && s.charAt(i) == s.charAt(i + 1)) {
        val palCount = 2 + f(i - 1, i + 2)
        m + (PalKey(i, palCount) -> i)
      } else {
        val palCount = 1 + f(i - 1, i + 1)
        m + (PalKey(i, palCount) -> i)
      }
    }
    index.take(n).keys.map { palKey =>
      Palindrome(s, palKey)
    }.toList
  }

  def naive(p: String => Boolean = const(true))(s: String): Vector[Palindrome] = {
    val endI = s.length

    @tailrec
    def f(i: Int, acc: Vector[Palindrome]): Vector[Palindrome] = {
      val xs = Vector.range(i, endI)
      val newAcc = xs.foldLeft(acc) { case (pals, j) =>
        val subS = s.substring(i, j + 1)
        if (p(subS)) pals :+ Palindrome(subS, i) else pals
      }

      if (i == endI) newAcc else f(i + 1, newAcc)
    }

    f(0, Vector.empty)
  }
}

PalindromesSpec.scala

import org.scalatest.FreeSpec

import scala.util.Random

class PalindromeSpec extends FreeSpec {
  import Palindrome._

  "Palindromes" - {
    "countMatchingChars" in {
      assertResult(2)(countMatchingChars("**ovo_*")(2, 4))
      assertResult(6)(countMatchingChars("**ovo**")(2, 4))
      assertResult(4)(countMatchingChars("hiballab")(3, 6))
    }

    "Can find palindromes of even length" in {
      val s = "*abuttubax-amanaplanacanalpanama-atoyotasatoyota*"
      assertResult(List("-amanaplanacanalpanama-","atoyotasatoyota", "abuttuba"))(
        longestPalindromes(s, 3).map(_.s))
    }

    "can find palindromes in a long string" in {
      val s = Random.alphanumeric.take(500000).mkString("")
      assert(longestPalindromes(s, 3).exists(_.s.length > 1))
    }
  }
}