Chaînes pondérées

Cette semaine, c'est Renaud qui vous propose un #KataOfTheWeek : Chaînes pondérées

Briefing du Kata : On définit le poids d'une chaîne de caractères alphabétiques comme la somme des poids de chaque lettre, où le poids d'une lettre est son rang dans l'alphabet.

Par exemple, la chaîne az a comme poids 1 + 26 = 27.

On appelle une chaîne uniforme une chaîne constituée d'un même caractère répété ou non. Par exemple, aaa et b sont des chaînes uniformes, mais pas aab.

L'entrée du problème consistera en une chaîne s (constituée de caractères latins minuscules non accentués), puis un entier n, et enfin une liste de n entiers sur n lignes. Soit E l'ensemble des poids de toutes les sous-chaînes uniformes contenues dans la chaîne s, vous devrez renvoyer, pour chaque entier i donné en entrée, "Yes" s'il appartient à E, et "No" autrement.

Par exemple, pour l'entrée suivante :

abbb
3
4
3
2

Ici, la chaîne s est abbb, puis la ligne suivante nous indique qu'il y aura n=3 entiers pour lesquels il faudra répondre "Yes" ou "No".

L'ensemble E dans ce cas comportera les poids des chaînes a, b, bb et bbb, soit [1, 2, 4, 6]. Vous devrez donc répondre en sortie :

Yes
No
Yes

Saurez-vous résoudre le problème ?

Bon courage !

Et sinon voici une solution proposée par l'auteur en Kotlin :

fun main(args: Array<String>) {
    val s = readLine()!!

    val queriesCount = readLine()!!.trim().toInt()

    val queries = Array<Int>(queriesCount, { 0 })
    for (i in 0 until queriesCount) {
        val queriesItem = readLine()!!.trim().toInt()
        queries[i] = queriesItem
    }

    val result = weightedUniformStrings(s, queries)

    println(result.joinToString("\n"))
}

fun weightedUniformStrings(s: String, queries: Array<Int>): Array<String> {
    val weights: MutableSet<Int> = mutableSetOf()
    var cursor = 0
    var index = 0
    while(index < s.length) {
        while(cursor < s.length && s[cursor] == s[index]) {
            weights.add((s[index].toInt() - 96) * (cursor - index + 1))
            cursor++
        }
        index = cursor
    }
    return queries.map { if (weights.contains(it)) "Yes" else "No" }.toTypedArray()
}

Votre équipe TakiVeille