Plus longue sous-chaîne sans répétitions
Suivre les dernières positions dans une fenêtre
Plus longue sous-chaîne sans répétitions est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Un problème classique de fenêtre
Trouvez la sous-chaîne la plus longue ne contenant aucun caractère répété. C'est un grand classique des fenêtres glissantes, présent dans presque tous les systèmes de correction. 🔤
Le piège de la force brute
Vérifier les doublons dans chaque sous-chaîne coûte environ O(n^2), voire davantage. Pour les longues chaînes, c'est beaucoup trop lent : un parcours plus astucieux est nécessaire.
Fenêtre de caractères uniques
Conservez une fenêtre qui contient toujours des caractères distincts. Étendez-la vers la droite et, lorsqu'un doublon apparaît, réduisez-la par la gauche jusqu'à sa disparition.
Mémoriser les dernières positions
Enregistrez le dernier indice de chaque caractère dans un dictionnaire. Vous saurez ainsi instantanément où un doublon a été vu pour la dernière fois pendant le parcours.
last = {}
left = 0
best = 0Parcourir chaque caractère
Parcourez la chaîne avec droite, en lisant à chaque étape l'indice et le caractère correspondant. Cela fait avancer la fenêtre d'une position à la fois.
for right, ch in enumerate(s):Faire avancer le pointeur gauche
Si le caractère a été vu à l'intérieur de la fenêtre actuelle, déplacez gauche juste après sa dernière position. Le doublon est ainsi supprimé en un seul déplacement.
if ch in last and last[ch] >= left:
left = last[ch] + 1Mettre à jour et mesurer
Enregistrez la nouvelle position de ce caractère : la fenêtre allant de gauche à droite ne contient alors plus de doublon. Sa longueur vaut droite moins gauche plus un.
last[ch] = right
best = max(best, right - left + 1)Pourquoi la vérification est importante
La vérification last[ch] >= left est essentielle. Sans elle, une ancienne position située hors de la fenêtre ferait reculer gauche à tort.
Temps et espace linéaires
Chaque caractère est visité une fois et gauche avance uniquement vers l'avant : le parcours est donc en O(n). Le dictionnaire utilise un espace proportionnel aux caractères distincts.
Couvrir les cas limites
Une chaîne vide donne zéro, et une chaîne composée d'une seule lettre répétée donne un. Vérifiez ces deux cas avant de soumettre votre solution pour éviter un WA sournois.
Le modèle réutilisable
La table des dernières positions, associée à un pointeur gauche qui avance par bonds, se généralise à de nombreux problèmes de caractères distincts, comme les fenêtres contenant au plus une répétition.
Vérification rapide
Vous mémorisez le dernier indice de chaque caractère pendant la recherche de la sous-chaîne unique la plus longue.
Récapitulatif
Faites glisser une fenêtre de caractères uniques, mémorisez chaque dernière position et faites avancer gauche au-delà des doublons. Cette méthode résout le problème classique en O(n). ✅
Questions Fréquemment Posées
La leçon « Plus longue sous-chaîne sans répétitions » est-elle gratuite ?
Oui — le texte complet de « Plus longue sous-chaîne sans répétitions » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Plus longue sous-chaîne sans répétitions » ?
Suivre les dernières positions dans une fenêtre Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « Plus longue sous-chaîne sans répétitions » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Sommes sur une fenêtre de taille fixe
- Fenêtre variable avec deux pointeurs
- Plus longue sous-chaîne sans répétitions
- Compter les fenêtres qui respectent une règle