Formations — 1 037 leçons en français

Accueil › Coding & algorithmique › La plus longue plage sans répétition

La plus longue plage sans répétition

Exercice de la série « Tableaux et parcours »avance

Le problème. Dans un flux de caractères, on veut la longueur de la plus longue plage contiguë où aucun caractère ne se répète.

Écrivez plusLonguePlage(s).

Appel Résultat attendu
plusLonguePlage("abcabcbb") 3 — "abc"
plusLonguePlage("bbbbb") 1
plusLonguePlage("pwwkew") 3 — "wke"
plusLonguePlage("abba") 2
plusLonguePlage("") 0

Ce qu'on attend. Une fenêtre de taille variable : on étend à droite tant que la condition tient, on rétrécit à gauche dès qu'elle est violée. Chaque caractère entre et sort au plus une fois, donc O(n).

Le piège. "abba" est le cas qui départage. En mémorisant la dernière position de chaque caractère, le bord gauche ne doit jamais reculer — et une position mémorisée peut être antérieure au bord actuel.

Cas de test

Écrire le code et le faire exécuter →

Votre code s'exécute réellement dans le navigateur, et la correction compare son résultat à celui d'une solution de référence.

La leçon qui prépare cet exercice

Les autres exercices de « Tableaux et parcours »