val input = "abccaaaba" // cccaaaba -> ccbaaba -> caaaba -> baaba -> caba -> bba -> bc -> a

val distinctChars = input.distinct.sorted.toList

@tailrec
def reduceString(acc: List[Char], seq: List[Char]): List[Char] = seq match {
  case Nil =>
    if (acc.toSet.size == 1) acc
    else reduceString(List.empty[Char], acc)
  case x :: Nil =>
    reduceString(acc :+ x, List.empty[Char])
  case x :: xs =>
    if (x != xs.head)
      reduceString(
        acc,
        distinctChars.diff(
          Seq(x, xs.headOption.getOrElse(List.empty[Char]))
        ) ++ Option(xs.tail).getOrElse(List.empty[Char])
      )
    else
      reduceString(x :: acc, xs)
}

println(reduceString(List.empty[Char], input.toCharArray.toList))