Partition Labels

+10

Vous disposez d’une chaîne s composée de lettres minuscules. Découpez-la en autant de parties consécutives que possible, de sorte que chaque lettre n’apparaisse que dans une seule partie : si une lettre apparaît dans une partie, toutes ses occurrences doivent se trouver dans cette partie. Retournez les longueurs des parties de gauche à droite.

Fonction

partitionLabels(s: string) → integer-array

sstring: la chaîne à découper, lettres minuscules uniquement
Renvoieinteger-array: la longueur de chaque partie, de gauche à droite

Contraintes

1 ≤ s.length ≤ 5 × 10⁴
s contient uniquement des lettres minuscules anglaises.
Les parties conservent leur ordre et, ensemble, constituent tout s, donc leurs longueurs s’additionnent pour donner s.length.

Exemples

Entrée: s = "abacdcefe"
Sortie: [3, 3, 3]
Explication: Les a se trouvent aux positions 0 et 2, les c aux positions 3 et 5 et les e aux positions 6 et 8 ; les coupures se font donc après aba et après cdc. Aucune partie ne peut être coupée à nouveau, car chacune commence et se termine par la même lettre.

+14 tests cachés à la soumission

Indices

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

0 sur 3 ouverts

Solution

Une coupure n’est permise que là où aucune lettre n’apparaît des deux côtés, et la meilleure réponse consiste à couper à chaque endroit de ce type. Tester chaque endroit en parcourant de nouveau la chaîne prend un temps quadratique. Commence par enregistrer la dernière position de chaque lettre, puis un seul parcours de gauche à droite permet de trouver toutes les coupures, car une partie doit s’étendre jusqu’à la dernière occurrence de chaque lettre qu’elle contient.

Testez chaque intervalle

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Il y a n-1 espaces entre les lettres voisines. Une coupure dans un espace n’est autorisée que si aucune lettre n’apparaît des deux côtés, car une lettre séparée par la coupure se retrouverait dans deux parties. Effectuer toutes les coupures autorisées donne le plus grand nombre de parties. Considérons une portion entre deux coupures autorisées voisines : aucune de ses lettres n’apparaît à gauche de la coupure de gauche ni à droite de celle de droite, donc toutes leurs occurrences se trouvent dans la portion et elle constitue une partie valide. Et toute réponse valide ne peut couper qu’aux espaces autorisés, donc aucune réponse ne comporte davantage de parties.

Il faut donc tester chaque espace : rassembler les lettres à sa gauche et à sa droite, puis couper si les deux ensembles n’ont aucun élément en commun. Dans abacdcefe, à l’espace après aba, il y a a et b à gauche, et c, d, e et f à droite. Rien n’est commun, donc on coupe. À l’espace après ab, il y a un a de chaque côté, donc on ne coupe pas.

Chaque test parcourt toute la chaîne, et il y a n-1 espaces, donc le travail représente environ n² lectures de lettres. Avec 50 000 lettres, cela fait 2,5 × 10^9 lectures, beaucoup trop lent pour les tests les plus grands.

Algorithme

Définis start = 0, où commence la partie actuelle.
Pour chaque coupure cut de 1 à n-1 (la coupure juste avant s[cut]), marque les lettres de s[0..cut-1] et les lettres de s[cut..n-1].
Si aucune lettre n’est marquée des deux côtés, ajoute cut-start à la réponse et définis start = cut.
Après la boucle, ajoute la dernière partie, n-start.

def partitionLabels(s):
    n = len(s)
    sizes = []
    start = 0  # where the current part begins
    for cut in range(1, n):  # the gap just before s[cut]
        left = set(s[:cut])
        right = set(s[cut:])
        if not (left & right):  # no letter on both sides: cut here
            sizes.append(cut - start)
            start = cut
    sizes.append(n - start)  # the last part has no gap after it
    return sizes

Fusionnez l’étendue de chaque lettre

Intuition

Considérez chaque lettre comme un intervalle, de sa première position à sa dernière. Une partie qui contient une lettre doit couvrir tout cet intervalle. Ainsi, deux lettres dont les intervalles se chevauchent doivent appartenir à la même partie, et le chevauchement se propage : si a chevauche b et b chevauche c, les trois se retrouvent dans une seule partie.

C’est le problème de fusion d’intervalles. En un seul parcours, notez la première et la dernière position de chaque lettre. Puis, prenez les intervalles dans l’ordre de leur position de départ et fusionnez ceux qui se chevauchent. Chaque bloc fusionné constitue une partie, et les espaces entre les blocs correspondent exactement aux coupures autorisées. Vous obtenez les intervalles dans l’ordre de leur position de départ sans effectuer de tri : parcourez à nouveau la chaîne et prenez l’intervalle d’une lettre lorsque vous arrivez à sa première position.

Dans codingisfun, les intervalles dans l’ordre sont c [0, 0], o [1, 1], d [2, 2], i [3, 6], n [4, 10], g [5, 5], s [7, 7], f [8, 8] et u [9, 9]. Les trois premiers restent isolés. À partir de i, chaque intervalle commence à la position 10 ou avant, où n se termine, donc ils fusionnent en [3, 10], une partie de 8 lettres.

La chaîne contient au plus 26 lettres différentes, donc il y a au plus 26 intervalles, et les tableaux des premières et dernières positions ont une taille fixe.

Algorithme

Lors d’un premier parcours de s, enregistre first et last, les première et dernière positions de chaque lettre.
Parcours à nouveau s. Lorsque la position i est la première position de sa lettre, l’intervalle de cette lettre [i, last] est le suivant dans l’ordre de début.
Si l’intervalle commence après le end du bloc actuel, ferme le bloc, de longueur end-start+1, et commence un nouveau bloc à i.
Dans les deux cas, définis end = max(end, last).
Ferme le dernier bloc et renvoie les longueurs.

def partitionLabels(s):
    first, last = {}, {}
    for i, c in enumerate(s):
        first.setdefault(c, i)
        last[c] = i
    sizes = []
    start = end = 0  # the block of merged spans being built
    for i, c in enumerate(s):
        if first[c] != i:
            continue  # take each letter's span once, at its first position
        if i > end:  # this span starts after the block: close the block
            sizes.append(end - start + 1)
            start = i
        end = max(end, last[c])
    sizes.append(end - start + 1)
    return sizes

Développez chaque partie jusqu’à sa dernière lettre

Intuition

Les premières positions ne sont pas nécessaires. Parcourez la chaîne de gauche à droite et conservez end, la position la plus éloignée de la dernière occurrence d’une lettre dans la partie en cours. Lorsque vous lisez une lettre à i, sa dernière occurrence doit aussi se trouver dans cette partie, alors augmentez end jusqu’à last[s[i]] si cette position est plus éloignée.

Lorsque i atteint end, chaque lettre lue dans cette partie a sa dernière occurrence à la position i ou avant. Aucune lettre ne traverse la séparation après i, une coupure à cet endroit est donc possible. Terminez la partie, de longueur end-start+1, et commencez la suivante à i+1.

Pourquoi couper dès que possible est-il le bon choix glouton ? Avant que i n’atteigne end, une lettre de la partie a encore une occurrence plus loin à droite, donc aucune coupure antérieure n’est possible. Et le parcours ne manque aucune séparation possible : si aucune lettre ne traverse la séparation après i, la dernière occurrence de chaque lettre de la partie se trouve à la position i ou avant, donc end est égal à i à cet endroit précis. Le parcours coupe exactement aux séparations possibles, ce qui donne le plus grand nombre de parties.

Dans abacdcefe, les dernières positions sont a 2, b 1, c 5, d 4, e 8 et f 7. La lecture de a fixe end à 2, b le laisse à cette valeur, et à i = 2, la partie se termine avec une longueur de 3. La lecture de c fixe end à 5 et la partie se termine à 5, avec là encore une longueur de 3. La partie contenant e se termine à 8.

Algorithme

En un seul parcours, stockez last[c], la dernière position de chaque lettre c, dans un tableau de 26 éléments.
Définissez start = 0 et end = 0.
Pour chaque position i, définissez end = max(end, last[s[i]]).
Si i == end, ajoutez end-start+1 à la réponse et définissez start = i+1.
Renvoyez les longueurs.

def partitionLabels(s):
    last = {c: i for i, c in enumerate(s)}  # last position of each letter
    sizes = []
    start = end = 0
    for i, c in enumerate(s):
        end = max(end, last[c])  # the part must reach c's last copy
        if i == end:  # no letter of this part appears later
            sizes.append(end - start + 1)
            start = i + 1
    return sizes

Pièges et cas limites

Le parcours glouton est court, donc les bugs se cachent dans la position à laquelle tu compares et dans la longueur des parties.

Couper lorsque tu atteins la dernière occurrence de la lettre courante au lieu de la end de la partie. Dans abcba, le c à l’index 2 est sa propre dernière occurrence, mais les a vont jusqu’à l’index 4 ; couper à cet endroit séparerait donc les a et les b.
Une erreur de décalage de un dans la longueur. Une partie allant de start à end, bornes incluses, contient end-start+1 lettres.
Renvoyer les positions de coupe au lieu des longueurs. Pour abacdcefe, la réponse est [3, 3, 3], et non [2, 5, 8].
Oublier la dernière partie lorsque tu coupes aux séparations. Il n’y a pas de séparation après la dernière partie, donc ajoute n-start une fois la boucle terminée.
S’attendre à avoir une partie par lettre distincte. zebraz contient cinq lettres différentes et une seule partie, car les z maintiennent ensemble tout ce qui se trouve entre eux.

Questions fréquentes4

Quelle est la complexité temporelle de Partition Labels ?

Un premier parcours enregistre la dernière position de chaque lettre et un second place les coupures, donc le temps est O(n). Le tableau des dernières positions comporte 26 entrées quelle que soit la longueur de la chaîne, donc l’espace supplémentaire est O(1), sans compter la sortie.

Pourquoi l’approche gloutonne fonctionne-t-elle pour les étiquettes de partition ?

La partie actuelle doit atteindre la dernière occurrence de chaque lettre qu’elle contient ; aucune coupure avant end n’est donc autorisée. À end, aucune lettre de la partie n’apparaît plus loin, la coupure est donc autorisée, et la faire ne nuit jamais au reste de la chaîne. Le parcours coupe donc à chaque endroit autorisé et nulle part ailleurs, ce qui donne le nombre maximal de parties possible.

Partition Labels est-il un problème de fusion d’intervalles ?

Oui, sous une forme déguisée. Chaque lettre couvre l’intervalle entre sa première occurrence et sa dernière, les intervalles qui se chevauchent doivent avoir une partie en commun, et leur fusion donne exactement les parties. Le parcours glouton effectue la même fusion au fur et à mesure : end est le bord droit du bloc fusionné jusqu’ici.

Combien de parties Partition Labels peut-il renvoyer ?

Entre 1 et 26. Aucune lettre ne peut apparaître dans deux parties, donc chaque partie possède au moins une lettre qui lui est propre, et il n’y a que 26 lettres minuscules. Une chaîne contenant chaque lettre une seule fois donne 26 parties de longueur 1, et une chaîne qui commence et se termine par la même lettre donne une seule partie.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

s = "abacdcefe"

Attendu

[3, 3, 3]

Partition Labels

Fonction

Contraintes

Exemples

Indices

Solution

Testez chaque intervalle

Fusionnez l’étendue de chaque lettre

Développez chaque partie jusqu’à sa dernière lettre

Pièges et cas limites

Questions fréquentes4

Problèmes similaires