Étant donné une chaîne de caractères s, trouvez la longueur du plus long sous-chaîne sans caractères répétés.

Exemple 1:

<strong>Entrée:</strong> s = "abcabcbb"
<strong>Sortie:</strong> 3 
<strong>Explication:</strong> Le plus long sous-chaîne sans caractères répétitifs est "abc", donc sa longueur est 3.

Exemple 2:

<strong>Entrée:</strong> s = "bbbbb"
<strong>Sortie:</strong> 1
<strong>Explication:</strong> Le plus long sous-chaîne sans caractères répétitifs est "b", donc sa longueur est 1.

Exemple 3:

<strong>Entrée:</strong> s = "pwwkew"
<strong>Sortie:</strong> 3
<strong>Explication:</strong> Le plus long sous-chaîne sans caractères répétitifs est "wke", donc sa longueur est 3.
Notez que votre réponse doit être la longueur d'un <strong>sous-chaîne</strong>, "pwke" est une <em>sous-séquence</em> et non une sous-chaîne.

Contraintes:

• 0 <= s.length <= 5 * 10^4
• La chaîne s se compose de lettres anglaises, de chiffres, de symboles et d'espaces

Ma solution

#include <iostream>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

int longueurSousChaineUnique(string chaine) {
    // Table de hachage pour stocker la dernière position de chaque caractère
    unordered_map<char, int> positionsCaracteres;
    longueurMax = 0; // Enregistre la longueur maximale du sous-chaîne
    debut = 0; // Pointeur gauche

    for (int fin = 0; fin < chaine.length(); ++fin) {
        caractereActuel = chaine[fin];
        // Vérifie si le caractère actuel existe déjà dans notre table
        if (positionsCaracteres.find(caractereActuel) != positionsCaracteres.end() && positionsCaracteres[caractereActuel] >= debut) {
            // Mettre à jour le pointeur gauche pour éviter les doublons
            debut = positionsCaracteres[caractereActuel] + 1;
        }
        // Mettre à jour la position du caractère actuel
        positionsCaracteres[caractereActuel] = fin;
        // Mettre à jour la longueur maximale
        longueurMax = max(longueurMax, fin - debut + 1);
    }

    return longueurMax;
}

int main(){
    string entree;
    cout << "Veuillez entrer une chaîne de caractères: ";
    cin >> entree;
    int resultat = longueurSousChaineUnique(entree);
    cout << "La longueur du plus long sous-chaîne sans caractères répétés est: " << resultat << endl;
    return 0;
}

Alternative solution

#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;

int longueurSousChaineUnique(const string& chaine) {
    unordered_set<char> caracteresUniques; // Stocke les caractères de la fenêtre actuelle
    longueurMax = 0;           // Enregistre la longueur maximale
    debut = 0;                // Pointeur gauche, limite gauche de la fenêtre

    for (int fin = 0; fin < chaine.length(); ++fin) {
        // Si le caractère est déjà présent, déplacer le pointeur gauche
        while (caracteresUniques.find(chaine[fin]) != caracteresUniques.end()) {
            caracteresUniques.erase(chaine[debut]);
            ++debut;
        }
        // Ajouter le caractère actuel à l'ensemble
        caracteresUniques.insert(chaine[fin]);
        // Mettre à jour la longueur maximale
        longueurMax = max(longueurMax, fin - debut + 1);
    }

    return longueurMax;
}

int main() {
    string test = "abcabcbb";
    int longueur = longueurSousChaineUnique(test);
    cout << "La longueur du plus long sous-chaîne sans caractères répétés est: " << longueur << endl;
    return 0;
}

Comparaison des approches

Les deux solutions utilisent une approche à deux pointeurs (sliding window), mais avec des implémentations différentes:

• La première solution utilise une table de hachage (unordered_map) pour stocker la dernière position de chaque caractère, permettant un accès direct et une mise à jour immédiate du pionteur gauche.
• La deuxième solution utilise un ensemble (unordered_set) pour vérifier les doublons et déplace le pointeur gauche jusqu'à ce que le caractère en double soit supprimé de l'ensemble.

La première méthode est généralement plus efficcae car elle évite la boucle while en sautant directement à la position appropriée.