basic string compression using the counts of repeated characters

StringCompression.scala

package arraystring

import org.scalatest.{Matchers, WordSpec}

import scala.annotation.tailrec
import scala.collection.mutable.StringBuilder

/**
  * basic string compression using the counts of repeated characters.
  * For example, the string aabcccccaaa would become a2b1c5a3.
  * three different implementation
  * Created by Arun Sethia on 7/7/18.
  */

trait StringCompression {

  /**
    * basic string compression using the counts of repeated characters.
    * For example, the string aabcccccaaa would become a2b1c5a3.
    * This function is using tailrecusion
    * Time Complexity - O(n)
    *
    * @param in
    * @return
    */
  def compressTailRecursion(in: String): String = {
    @tailrec
    def computeCompress(data: List[Char], lastChar: Char, lastCharCount: Int, acc: List[String]): List[String] = {
      data match {
        case Nil => (lastChar + lastCharCount.toString) :: acc
        case h :: _ => {
          if (h == lastChar) {
            computeCompress(data.tail, h, lastCharCount + 1, acc)
          }
          else {
            val prevCompress = new StringBuilder(lastChar.toString).append(lastCharCount.toString).toString
            computeCompress(data.tail, h, 1, prevCompress :: acc)
          }
        }
      }
    }
    if (in.length >= 1) {
      val inputChars = in.toList
      computeCompress(inputChars.tail, inputChars.head, 1, List.empty[String]).reverse.mkString
    } else {
      in
    }
  }

  /**
    * basic string compression using the counts of repeated characters.
    * For example, the string aabcccccaaa would become a2b1c5a3.
    * This function is using foldLeft
    * Time Complexity - O(n)
    *
    * @param in
    * @return
    */
  def compressString(in: String): String = {
    val revList = in.toList.foldLeft(List.empty[(Char, Int)])((tupList, strCh) => {
      tupList match {
        case ((lch, cnt) :: t) if strCh == lch => (lch, cnt + 1) :: t
        case _ => (strCh, 1) :: tupList
      }
    })
    val respStr = revList.reverse.foldLeft(new StringBuilder()) {
      (sb, tup) => sb.append(tup._1).append(tup._2)
    }
    respStr.toString
  }

  /**
    * basic string compression using the counts of repeated characters.
    * For example, the string aabcccccaaa would become a2b1c5a3.
    * This function is using foldLeft
    * Time Complexity - O(n)
    *
    * @param in
    * @return
    */
  def compressFoldLeft(in: String) = {
    val (acc, count, lastChar) = in.toList.foldLeft((new StringBuilder, 0, in.toList.head)) {
      case ((acc, lastCharCount, lastChar), h) => {
        if (h == lastChar) (acc, lastCharCount + 1, h)
        else {
          val prevCompress = new StringBuilder(lastChar.toString).append(lastCharCount.toString).toString
          (acc.append(prevCompress), 1, h)
        }
      }
    }
    acc.append(lastChar).append(count).toString
  }
}

class StringCompressionSpec extends WordSpec
  with Matchers
  with StringCompression {

  Array.ofDim[Int](10, 10)
  "aabcccccaaa" should {
    "return a2b1c5a3" in {
      assert(compressFoldLeft("aabcccccaaa") == "a2b1c5a3")
    }
    "return a2b1c5a3 using recursions" in {
      assert(compressTailRecursion("aabcccccaaa") == "a2b1c5a3")
    }
  }

  def isSubString(s: String, s2: String) = {
    s.contains(s2)
  }

}