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
["abcabcbb"]["bbbbb"]["pwwkew"]["abba"][""]["a"]
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.