Longest Substring Without Repeating Characters

+10

Vous obtenez une chaîne s. Trouvez la plus longue sous-chaîne, une suite de caractères qui se suivent, dans laquelle aucun caractère n’apparaît deux fois, et renvoyez sa longueur.

Les lettres majuscules et minuscules comptent comme des caractères différents, donc a et A ne sont pas une répétition.

Fonction

lengthOfLongestSubstring(s: string) → integer

sstring: la chaîne à rechercher
Renvoieinteger: la longueur de la plus longue sous-chaîne sans caractère répété

Contraintes

1 ≤ s.length ≤ 5 × 10⁴
s contient uniquement des lettres anglaises (minuscules et majuscules) et des chiffres.
Les lettres majuscules et minuscules sont des caractères différents.

Exemples

Entrée: s = "coddycode"
Sortie: 5
Explication: ycode contient cinq caractères différents. En ajoutant d devant, on obtient dycode, avec d deux fois, et aucune autre suite de cinq caractères ou plus n’évite une répétition.

Entrée: s = "racecar"
Sortie: 4
Explication: race et ecar comportent toutes deux quatre lettres différentes. Chaque suite de cinq lettres contient deux fois la même lettre.

Entrée: s = "a1b2a3b"
Sortie: 5
Explication: Les chiffres comptent aussi comme des caractères, donc 1b2a3 en contient cinq différents. Les deux séquences de six contiennent chacune un deuxième a ou un deuxième b.

Pour aller plus loin

Que changerais-tu si s pouvait contenir n’importe quel caractère Unicode au lieu de lettres et de chiffres ?

Solution

Maintenez une fenêtre : deux bords autour d’une séquence sans caractère répété. Le bord droit lit chaque caractère une seule fois et le bord gauche avance uniquement, donc un seul parcours trouve, pour chaque fin, la plus longue séquence sans répétition qui se termine à cet endroit.

Vérifiez chaque sous-chaîne

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Essayez chaque début et chaque fin, et testez chaque sous-chaîne en ajoutant ses caractères à un ensemble jusqu’à ce que l’un d’eux s’y trouve déjà. Chaque candidate est testée, donc la plus longue sous-chaîne valide ne peut pas être manquée.

Il y a environ n²/2 sous-chaînes, soit 1.25 × 10^9 pour n = 5 × 10^4, et un test peut lire jusqu’à n caractères : O(n³). Ici, un test s’arrête après au plus 63 caractères, puisque la chaîne ne contient que 62 caractères différents, mais cela représente tout de même plus d’un milliard de tests.

Algorithme

Définis best à 0.
Pour chaque indice de départ, parcours chaque indice de fin, du début à la fin de la chaîne.
Ajoute les caractères de la sous-chaîne un par un à un ensemble vide, et arrête-toi au premier caractère déjà présent dans l’ensemble.
Si aucun caractère ne se répète et que la sous-chaîne dépasse best, stocke sa longueur.
Retourne best.

def lengthOfLongestSubstring(s):
    def has_no_repeat(start, end):
        seen = set()
        for k in range(start, end + 1):
            if s[k] in seen:
                return False
            seen.add(s[k])
        return True

    best = 0
    n = len(s)
    for start in range(n):
        for end in range(start, n):
            if has_no_repeat(start, end):
                best = max(best, end - start + 1)
    return best

Fenêtre glissante avec un ensemble

Intuition

Si abc ne contient aucune répétition, tester abcd nécessite une seule question : est-ce que d se trouve parmi a, b et c ? Un ensemble des caractères de la fenêtre répond instantanément à cette question.

Déplace right d'un pas à la fois. Si le nouveau caractère se trouve dans l'ensemble, supprime des caractères depuis la gauche jusqu'à ce que sa copie précédente ait disparu, puis ajoute-le et mesure. Tu ne supprimes des caractères que lorsque c'est nécessaire, donc pour chaque right, la fenêtre est la plus longue suite sans répétition qui se termine à cet endroit, et la meilleure sous-chaîne se termine quelque part. Chaque caractère entre une fois dans l'ensemble et en sort au plus une fois : O(n).

Algorithme

Commence avec un ensemble vide, left = 0 et best = 0.
Parcours chaque indice avec right.
Tant que s[right] se trouve dans l’ensemble, supprime s[left] et avance left d’un pas.
Ajoute s[right] à l’ensemble.
Si right - left + 1 est supérieur à best, mémorise-le.
Renvoie best.

def lengthOfLongestSubstring(s):
    in_window = set()  # the characters between left and right
    left = 0
    best = 0
    for right in range(len(s)):
        # Shrink from the left until s[right] is no longer inside.
        while s[right] in in_window:
            in_window.remove(s[left])
            left += 1
        in_window.add(s[right])
        best = max(best, right - left + 1)
    return best

Fenêtre glissante qui passe au dernier index observé

Intuition

Tu sais déjà où left doit arriver : juste après la copie précédente du nouveau caractère. Stocke l’indice de dernière occurrence de chaque caractère dans une map ou dans un tableau avec une case par code de caractère, et left y saute en une seule étape.

Ne saute que si cet indice est supérieur ou égal à left. Une copie plus ancienne se trouve déjà hors de la fenêtre, et y sauter ferait reculer left. À chaque étape, la fenêtre est celle que construit la version avec un ensemble, et chaque caractère nécessite désormais une consultation, une comparaison et une écriture.

Algorithme

Crée une map vide associant chaque caractère à son dernier indice, puis définis left = 0 et best = 0.
Parcours chaque indice avec right et lis le caractère ch à cet emplacement.
Si ch a été vu pour la dernière fois à l’indice left ou après, définis left sur cet indice plus un.
Enregistre right comme dernier indice de ch.
Si right - left + 1 est supérieur à best, enregistre cette valeur.
Renvoie best.

def lengthOfLongestSubstring(s):
    last_seen = {}
    start = 0
    best = 0
    for i, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= start:
            start = last_seen[ch] + 1
        last_seen[ch] = i
        if i - start + 1 > best:
            best = i - start + 1
    return best

Pièges et cas limites

Déplacer left vers l’arrière. Dans abba, le premier a à l’index 0 est déjà hors de la fenêtre lorsque tu atteins le dernier a. Passer à l’index 1 ramène le deuxième b dans la fenêtre et donne 3 au lieu de 2.
Compter la fenêtre comme right - left. Les deux extrémités en font partie, alors ajoute un.
Mettre d’abord la chaîne en minuscules. a et A sont des caractères différents ici, donc aA a une longueur de 2.
Mesurer uniquement lorsqu’un caractère répété apparaît. Une chaîne sans répétition, comme z, ne déclenche jamais cette mesure, et la réponse est 0.

Questions fréquentes3

Quelle est la complexité temporelle de la plus longue sous-chaîne sans caractères répétés ?

La fenêtre glissante s’exécute en temps O(n), où n est la longueur de la chaîne : le bord droit lit chaque caractère une seule fois et le bord gauche ne se déplace que vers l’avant. L’espace supplémentaire est de O(k), où k est le nombre de caractères différents que la chaîne peut contenir, soit 62 ici.

Faut-il utiliser une table de hachage ou un tableau pour les derniers indices ?

Les deux offrent un temps d’exécution en O(n). Avec un petit ensemble fixe de caractères, comme ici, un tableau indexé par code de caractère évite le hachage et est plus rapide.

Quelle est la différence entre une sous-chaîne et une sous-séquence ?

Une sous-chaîne est un bloc de caractères qui se suivent, comme ode dans coddycode. Une sous-séquence peut ignorer des caractères, comme cdy. Ce problème porte sur une sous-chaîne, c’est pourquoi une fenêtre avec deux extrémités convient.

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

Test #1

Test #2

Test #3

Argument

s = "coddycode"

Résultat attendu

Longest Substring Without Repeating Characters

Fonction

Contraintes

Exemples

Indices

Solution

Vérifiez chaque sous-chaîne

Fenêtre glissante avec un ensemble

Fenêtre glissante qui passe au dernier index observé

Pièges et cas limites

Questions fréquentes3

Problèmes similaires