String Compression

Q: Quelle est la complexité temporelle de la compression de chaînes ?

Le parcours à deux pointeurs prend un temps de O(n) , car l’index de parcours ne fait qu’avancer. En dehors du résultat, il conserve deux index, donc l’espace supplémentaire est de O(1) .

FacileDeux pointeurs Tableaux et chaînes

+10

Tu reçois une chaîne s composée de lettres anglaises. Compresse-la : remplace chaque suite d’au moins deux lettres identiques consécutives par cette lettre suivie de la longueur de la suite, et laisse telle quelle une lettre qui apparaît seule. Ainsi, aabccc devient a2bc3. Renvoie la chaîne compressée.

Les majuscules et les minuscules sont des lettres différentes : aA correspond à deux suites de longueur 1.

Fonction

compress(s: string) → string

sstring: la chaîne à compresser, lettres anglaises uniquement
Renvoiestring: la chaîne compressée, chaque séquence étant écrite sous la forme de sa lettre suivie de sa longueur lorsque celle-ci est supérieure à 1

Contraintes

1 ≤ s.length ≤ 2 × 10⁴
s ne contient que des lettres anglaises, de a à z et de A à Z.
Une longueur de séquence est écrite en décimal et peut comporter plusieurs chiffres.

Exemples

Entrée: s = "aabccc"
Sortie: "a2bc3"
Explication: Les séquences sont aa, b et ccc. Elles deviennent a2, b (une lettre isolée n’a pas de compteur) et c3.

Entrée: s = "abbbbbbbbbbbb"
Sortie: "ab12"
Explication: Un a, puis douze b. La longueur 12 s’écrit avec les deux caractères 1 et 2, donc le résultat est ab12.

Entrée: s = "zzZZZ"
Sortie: "z2Z3"
Explication: La lettre minuscule z et la lettre majuscule Z sont différentes, donc il s’agit d’une suite de deux suivie d’une suite de trois : z2Z3.

Pour aller plus loin

Écrivez l’opération inverse : à partir d’une chaîne compressée telle que ab12, reconstruisez l’originale. Comment lire un nombre de répétitions composé de plusieurs chiffres ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Trouvez où commence et où se termine chaque suite de lettres identiques, puis écrivez sa longueur sous forme de texte. Une suite d’une seule lettre ne reçoit aucun décompte, et un décompte peut comporter plusieurs chiffres. Deux index, l’un au début d’une suite et l’autre qui parcourt celle-ci jusqu’à sa fin, permettent de le faire en un seul passage.

Rassemble les séries, puis écris-les

Intuition

Commence par enregistrer les séquences sous forme de paires composées d’une lettre et d’une longueur : pour aabccc, (a, 2), (b, 1), (c, 3). Chaque lettre prolonge la dernière séquence ou en ouvre une nouvelle. Écris ensuite la lettre de chaque séquence, suivie de sa longueur si elle est supérieure à 1.

Les deux parcours sont en O(n). La liste peut contenir n séquences lorsqu’aucune lettre adjacente ne correspond ; elle nécessite donc un espace supplémentaire de O(n).

Algorithme

Crée une liste vide de séquences.
Pour chaque lettre de s : si la dernière séquence contient la même lettre, ajoute 1 à sa longueur ; sinon, ajoute une nouvelle séquence de longueur 1.
Pour chaque séquence, écris sa lettre, puis sa longueur en notation décimale si elle est supérieure à 1.

def compress(s):
    # First pass: collect the runs as [letter, length] pairs
    runs = []
    for ch in s:
        if runs and runs[-1][0] == ch:
            runs[-1][1] += 1
        else:
            runs.append([ch, 1])
    # Second pass: write each run, with its length when it is more than 1
    parts = []
    for letter, length in runs:
        parts.append(letter)
        if length > 1:
            parts.append(str(length))
    return "".join(parts)

Deux pointeurs sur chaque séquence

Intuition

Garde i à la première lettre du groupe courant et avance j tant que s[j] est égal à s[i]. Lorsque j s’arrête, sur une lettre différente ou à la fin, la longueur du groupe est j-i. Écris-la et définis i = j. Pour abbbbbbbbbbbb, j s’arrête d’abord à 1, ce qui donne a, puis à 13, ce qui donne b12.

Le dernier groupe ne nécessite aucun cas particulier, car la boucle interne s’arrête à la fin de la chaîne. j ne fait qu’avancer, donc le temps d’exécution est O(n), et en plus du résultat, tu conserves deux index. Les versions en R et en Swift divisent d’abord s en un tableau de caractères ; elles utilisent donc un espace supplémentaire de O(n).

Algorithme

Définissez i = 0.
Tant que i se trouve dans la chaîne, définissez j = i et avancez j tant qu’il se trouve dans la chaîne et que s[j] est égal à s[i].
Écrivez s[i] ; si j-i est supérieur à 1, écrivez-le sous forme de texte décimal.
Définissez i = j et recommencez.

def compress(s):
    parts = []
    n = len(s)
    i = 0
    while i < n:
        # Move j to the first index after the run that starts at i
        j = i
        while j < n and s[j] == s[i]:
            j += 1
        parts.append(s[i])
        if j - i > 1:
            parts.append(str(j - i))
        i = j
    return "".join(parts)

Pièges et cas limites

Écrire une séquence uniquement lorsque tu rencontres une lettre différente. Rien ne suit le dernier ccc de aabccc, donc tu renvoies a2b.
Écrire le compte sur un seul caractère, par exemple '0' + count. Cela échoue à 10 : douze b nécessitent les deux caractères 12.
Écrire 1 après une lettre isolée. b reste b, et non b1.
Ignorer la casse. zzZZZ donne z2Z3, et non z5.
Faire croître une chaîne immuable avec +, comme en Java ou en C#. Chaque + copie le résultat obtenu jusque-là, ce qui rend la boucle O(n²) ; utilise un générateur de chaînes.

Questions fréquentes3

Quelle est la complexité temporelle de la compression de chaînes ?

Le parcours à deux pointeurs prend un temps de O(n), car l’index de parcours ne fait qu’avancer. En dehors du résultat, il conserve deux index, donc l’espace supplémentaire est de O(1).

La chaîne compressée peut-elle être plus longue que l’originale ?

Pas dans cette version. Une lettre isolée reste un caractère, et une suite de k ≥ 2 lettres devient une lettre suivie des chiffres de k, jamais plus de k caractères. Un schéma qui écrit un compte après chaque lettre, comme a1b1, peut doubler la longueur.

Comment compresser une chaîne en place ?

Utilise un tableau de caractères avec un index de lecture et un index d’écriture. Parcours chaque série avec l’index de lecture, puis écris sa lettre et les chiffres de sa longueur à l’index d’écriture. La sortie n’est jamais plus longue que l’entrée lue jusqu’alors, donc l’index d’écriture ne dépasse jamais l’index de lecture. Renvoie la nouvelle longueur à la fin.

def compress(s):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Argument

s = "aabccc"

Résultat attendu

"a2bc3"