Условие

Дана строка s, состоящая из символов 'I' (увеличение) и 'D' (уменьшение). Требуется построить перестановку массива perm из чисел от 0 до n (где n — длина строки s), такую, что:

• Если s[i] == 'I', то perm[i] < perm[i + 1]

• Если s[i] == 'D', то perm[i] > perm[i + 1]

Верните любую допустимую перестановку perm.

Примеры

Input: s = "IDID” Output: [0,4,1,3,2]

Input: s = "III” Output: [0,1,2,3]

Input: s = "DDI” Output: [3,2,0,1]

Решение

fun diStringMatch(s: String): IntArray {
    val n = s.length
    val result = IntArray(n + 1)
    var low = 0
    var high = n

    for (i in s.indices) {
        if (s[i] == 'I') {
            result[i] = low
            low++
        } else {
            result[i] = high
            high--
        }
    }
    result[n] = low // или high, так как low и high должны быть равны

    return result
}

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

O(n), где n — длина строки s, поскольку мы проходим по строке один раз.

Пространственная сложность

O(n), так как мы используем массив result длиной n + 1 для хранения перестановки.