Write a method to replace all spaces in a string with '%20'

URLify.scala

/**
  * Write a method to replace all spaces in a string with '%20: 
  * You may assume that the string has sufficient space at the end to hold the additional characters
  * Input: "hello world   " 
  * Output: "hello%20world"
  * Created by Arun Sethia on 7/5/18.
  */
trait URLify {

  /**
    * total time complexity O(3n) ~= O(n)
    *
    * @param input
    * @return
    */
  def buildURLify(input: String): String = {
    val data = removeTrailSpace(input)
    //O(n)
    data.foldLeft(new StringBuilder) {
      case (builder, ' ') => builder.append("%20")
      case (builder, x) => builder.append(x)
    }.toString()
  }

  /**
    * remove trail space O(n+n)=O(2n)
    *
    * @param in
    * @return
    */
  private def removeTrailSpace(in: String): List[Char] = {
    @tailrec
    def space(in: List[Char]): List[Char] = {
      //worst case O(n)
      in match {
        case h :: t if (h == ' ') => space(t)
        case h :: t if (h != ' ') => in
      }
    }
    //O(n)
    space(in.reverse.toList).reverse
  }
}