LeetCode Problem: 763. Partition Labels

Problem description can be found here.
What we need to do:

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Here is a solution in Scala:

object Solution {
  def partitionLabels(S: String): List[Int] = {
    def lastChar(S: String): Map[Char, Int] = {
      S.zipWithIndex
        .groupBy(a => a._1)
        .mapValues(_.max)
        .values
        .toMap
    }

    def solve(S: String, i: Int, j: Int, part: Int, res: List[Int], last: Map[Char, Int]): List[Int] = {
      if (i >= S.length) res
      else {
        val nj: Int = j max last(S(i))
        if (i == nj) solve(S, i + 1, nj, i + 1, res ::: List((i - part + 1)), last)
        else solve(S, i + 1, nj, part, res, last)
      }
    }
    solve(S, 0, 0, 0, Nil, lastChar(S))
  }
}

Given a string lastChar method returns a map, where key is the character and its value is index of last occurrence of that character in the string S.

For string :"ababcbacadefegdehijhklij" lastChar method will return this map :

Map(e -> 15, j -> 23, f -> 11, a -> 8, i -> 22, b -> 5, g -> 13, l -> 21, c -> 7, h -> 19, k -> 20, d -> 14)

Now we traverse over the string and checks last occurrence of that char using the map we got from lastChar, and we store last index in j. Whenever current index and j is equal, we can say that partition is possible at index i. So we store the number of character in the List res and move to the next index. when we reach the last index we simply returns the List res.