Ensure Minimum Separation

EnsureMinimumSeparation.scala

object EnsureMinimumSeparation {
  case class CountedString(data: Char, count: Int) extends Comparable[CountedString] {
    override def compareTo(o: CountedString): Int = {
      if (count != o.count) {
        count - o.count
      } else {
        o.data - data
      }
    }
  }

  def buildHisto(s: String): Map[Char, Int] = {
    s.foldLeft(Map[Char, Int]()) { case (map, c) =>
      if (map.contains(c)) {
        map + (c -> (map(c) + 1))
      } else {
        map + (c -> 1)
      }
    }
  }

  def ensureMinimumSeparation(input: String, minSep: Int): String = {
    val histo: Map[Char, Int] = buildHisto(input)
    val set: mutable.PriorityQueue[CountedString] = mutable.PriorityQueue[CountedString]()
    histo.foreach(h => set.enqueue(CountedString(h._1, h._2)))
    val queue: mutable.ListBuffer[CountedString] = mutable.ListBuffer[CountedString]()
    val output = mutable.ListBuffer[Char]()

    while(set.nonEmpty) {
      val head: CountedString = set.dequeue()
      output.append(head.data)
      if (queue.size == minSep) {
        val cs = queue.remove(0)
        if (cs.count > 0) {
          set.enqueue(cs)
        }
      }
      queue.append(head.copy(count = head.count - 1))
    }

    if (output.size != input.size) {
      throw new IllegalStateException("Impossible")
    }

    output.mkString
  }
}

EnsureMinimumSeparationTest.scala

class EnsureMinimumSeparationTest extends FunSpecLike with ShouldMatchers {
  describe("The Solver") {
    it("should solve a simple case") {
      val separation: String = EnsureMinimumSeparation.ensureMinimumSeparation("AAB", 1)
      separation shouldEqual "ABA"
    }

    it("should solve a more complex case") {
      EnsureMinimumSeparation.ensureMinimumSeparation("ABCCC", 1) shouldEqual "CACBC"
    }

    it("should ensure lowest alphabetical ordering") {
      EnsureMinimumSeparation.ensureMinimumSeparation("BACCC", 1) shouldEqual "CACBC"
    }
  }
}