

class Solution {
    fun partitionLabels(S: String): List<Int> {
        val lettersIntervals = MutableList<Pair<Int,Int>>(26) { _ -> Pair(Int.MAX_VALUE,Int.MIN_VALUE)}
        val result = mutableListOf<Int>()

        for(i in 0 until S.length){
            val index = S[i]-'a'
            if(lettersIntervals[index].first == Int.MAX_VALUE){
                lettersIntervals[index] = Pair(i,i)
            }else{
                lettersIntervals[index] = Pair(lettersIntervals[index].first,i)
            }
        }

        val intervals = mutableListOf<Pair<Int,Int>>()
        val mergedIntervals = mutableListOf<Pair<Int,Int>>()

        for(inter in lettersIntervals){
            if(inter.first != Int.MAX_VALUE){
                intervals.add(inter)
            }
        }

        intervals.sortWith(Comparator{ p1: Pair<Int,Int>, p2: Pair<Int,Int> ->
            if(p1.first == p2.first) p1.second - p2.second
            else p1.first - p2.first
        })  

        var currInterval = intervals.first()

        for(i in 1 until intervals.size){
            val inter = intervals[i]
            if(currInterval.second>inter.first){
                val first = Math.min(currInterval.first,inter.first)
                val second = Math.max(currInterval.second,inter.second)
                currInterval = Pair(first,second)
            }else{
                mergedIntervals.add(currInterval)
                currInterval = inter
            }
        }

        mergedIntervals.add(currInterval)
        for(inter in mergedIntervals){
            result.add(inter.second - inter.first+1)
        }

        return result
    }
}

fun main(args: Array<String>) {
    val word = "ababcbacadefegdehijhklij"
    val sol = Solution()
    println(sol.partitionLabels(word))
}