Условие

Лёша сидел на лекции. Ему было невероятно скучно. Голос лектора казался таким далёким и незаметным...

Чтобы окончательно не уснуть, он взял листок и написал на нём свое любимое слово. Чуть ниже он повторил своё любимое слово, без первой буквы. Ещё ниже он снова написал своё любимое слово, но в этот раз без двух первых и последней буквы.

Тут ему пришла в голову мысль — времени до конца лекции все равно ещё очень много, почему бы не продолжить выписывать всеми возможными способами это слово без какой-то части с начала и какой-то части с конца?

После лекции Лёша рассказал Максу, как замечательно он скоротал время. Максу стало интересно посчитать, сколько букв каждого вида встречается у Лёши в листочке. Но к сожалению, сам листочек куда-то запропастился.

Макс хорошо знает любимое слово Лёши, а ещё у него не так много свободного времени, как у его друга, так что помогите ему быстро восстановить, сколько раз Лёше пришлось выписать каждую букву.

Примеры

Ввод: hello Вывод: e: 8 h: 5 l: 17 o: 5

Ввод: abacaba Вывод: a: 44 b: 24 c: 16

Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    val s = reader.readLine()
    val n = s.length
    val count = mutableMapOf<Char, Long>()

    for (i in s.indices) {
        val contrib = (i + 1).toLong() * (n - i) // Сколько раз буква участвует в подпоследовательностях
        count[s[i]] = count.getOrDefault(s[i], 0) + contrib
    }

    for ((char, freq) in count.toSortedMap()) {
        writer.write("$char: $freq")
        writer.newLine()
    }

    reader.close()
    writer.close()
}