scala - Counting occurences of characters in a String using tail recursion

Question

I have no clue how to count the occurrences of characters in a string using tail recursion in scala.

I need to run a program with input

times(explanation)

and the output is:

List((e,1), (x,1), (p,1), (l,1), (a,2), (n,2), (t,1), (i,1), (o,1))

I tried running RLE so far but the topic of tail recursion is new to me, so some steps/algorithm for doing so would be perfect

Answer 1

Possible Solutions:

A String is a list of characters. Group them by identity which is (x => x), then count them. Normally groupBy returns a Map which can by transformed to a list of tuples by toList.

Code/ not reinventing the wheel

def times(s: String) = s.groupBy(identity).mapValues(_.size).toList 
times: (s: String)List[(Char, Int)]

Example

times("explanation")
res1: List[(Char, Int)] = List((e,1), (x,1), (n,2), (t,1), (a,2), (i,1), (l,1), (p,1), (o,1))

Code with tail recursion / reinvents the wheel/ please use not to cheat in the Coursera Scala Course

import scala.annotation.tailrec

def myTimes(s: String) : List[(Char,Int)] = {

  @tailrec // comiler cheks if really tailrecursive
  def timesTail(chars: List[Char], res: List[(Char,Int)])  : List[(Char,Int)] = 
    chars match {
      case Nil => res      // we are done when there are no characters left
      case char :: rest => {
          // otherwise 
          val newCharCount = 
            res.
              find (_._1 == char). //check if we already have seen the character
              map{ case (c,count) => (c,count + 1)  }. // if yes, we raise take the old count and raise it by one
              getOrElse( (char,1) ) // otherwise we count one occurrence
          // here it gets recursive 
          timesTail(
                rest, // remaining Characters
                newCharCount :: res.filterNot(_._1 == char) // add the new count to list, remove old if present
          )
      }
    }
  // initial call with empty lsit to start the helper function  
  timesTail(s.toList,List())

}