on
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
.