Find the most frequent character in a string

Question

I'm trying to solve this problem https://community.topcoder.com/stat?c=problem_statement&pm=40

Given a string made up of ONLY letters and digits, determine which character is repeated the most in the string ('A' is different than 'a'). If there is a tie, the character which appears first in the string (from left to right) should be returned.

Here is my approach is Scala. I feel it's not very functional, and slow(because of a new reversed String object).

def findMaxFunctional(word: String): Char = {
 var curMaxCount, maxCharId = 0
 word.reverse.foldLeft(new Array[Int](128))((acc, ch) => {
 acc(ch) = acc(ch) + 1
 if(acc(ch) >= curMaxCount) {
 curMaxCount = acc(ch)
 maxCharId = ch
 }
 acc
 })
 maxCharId.toChar
 }

Answer 1

Instead of reversing the input string you could foldRight over it, and instead of updating mutable variables let the fold accumulator carry the current data forward. As an Array is mutable by default there's no point in having the fold accumulator make copies in order to carry it forward.

def findMaxFunctional(word: String): Char = {
 val arr = new Array[Int](128)
 word.foldRight((' ', 0)){
 case (c, (mxChr, mxCnt)) =>
 arr(c) += 1
 if (arr(c) >= mxCnt) (c, arr(c))
 else (mxChr, mxCnt)
 }._1
}

Answer 2

You forgot to resolve a possible tie.

There is no need to recompute the max value within your fold-loop at each iteration. You just fill your array and at the very end get the maximum.

You are using fold as a basic for-loop since your accumulator is actually the same array at each iteration.

Your code is not quite functional in the sense that you use mutable state instead of immutable state.

And why not just string.groupBy(identity).mapValues(_.size)? You can have multiple values with the maximal size, and then you have to do something else to resolve the ties.