Условие

Дана строка s, состоящая только из строчных букв.

Построй новую строку по следующему алгоритму, пока s не станет пустой:

1. Найди самый маленький символ среди оставшихся и добавь его в результат.
2. Повтори с следующими по возрастанию символами, пока не дойдёшь до максимального.
3. Теперь делай то же самое в обратном порядке — от максимального к минимальному.
4. Повторяй шаги 1–3, пока не использованы все символы.

Верни полученную строку.

Примеры

Input: s = "aaaabbbbcccc” Output: "abccbaabccba” Explanation: сначала по возрастанию: abc, потом по убыванию: cba, и так далее.

Input: s = "rat” Output: "art” Explanation: Слово «rat» превращается в «art» после переупорядочивания согласно указанному алгоритму.

Решение

fun sortString(s: String): String {
    // Частота символов
    val count = IntArray(26)
    for (c in s) {
        count[c - 'a']++
    }

    val result = StringBuilder()
    val total = s.length

    while (result.length < total) {
        // Прямой проход: от 'a' к 'z'
        for (i in 0..25) {
            if (count[i] > 0) {
                result.append('a' + i)
                count[i]--
            }
        }
        // Обратный проход: от 'z' к 'a'
        for (i in 25 downTo 0) {
            if (count[i] > 0) {
                result.append('a' + i)
                count[i]--
            }
        }
    }

    return result.toString()
}

Временная сложность

O(n * k), где n — длина строки, k = 26 — алфавит; можно считать O(n).