La tâche consiste à identifier le premier caractère non répétitif au sein d'une chaîne de caractères donnée et à renvoyer son indice. Si aucun caractère unique n'est trouvé, la fonction doit retourner -1.

Exemples :

• s = "leetcode" retourne 0 (le caractère 'l' est le premier unique)
• s = "loveleetcode" retourne 2 (le caractère 'v' est le premier unique)

Note : Il est supposé que la chaîne ne contient que des letres minuscules.

Approche 1 : Utilisation d'un Tableau de Fréquences

Cette méthode consiste à compter la fréquence de chaque caractère dans la chaîne en utilisant un simple tableau d'entiers de taille 26 (pour les 26 lettres de l'alphabet minuscule). Après avoir rempli le tableau, une seconde itération sur la chaîne permet de trouver le premier caractère dont le compte est égal à 1 dans le tableau de fréquences. Son indice est alors retourné.

public class SolutionCaractereUnique {
    public int trouverPremierUniqueParTableau(String entree) {
        int[] occurrences = new int[26]; // Tableau pour stocker la fréquence de chaque lettre (a-z)

        // Première passe : Compter les occurrences de chaque caractère
        for (char c : entree.toCharArray()) {
            occurrences[c - 'a']++;
        }

        // Deuxième passe : Trouver le premier caractère qui apparaît une seule fois
        for (int i = 0; i < entree.length(); i++) {
            if (occurrences[entree.charAt(i) - 'a'] == 1) {
                return i; // Retourne l'indice du premier caractère unique
            }
        }
        return -1; // Aucun caractère unique n'a été trouvé
    }
}

Approche 2 : Utilisation d'une Carte de Hachage (HashMap) pour les Fréquences

Similaire à la première approche, mais utilisant une HashMap pour stocker la fréquence des caractères. Cela offre plus de flexibilité si l'ensemble des caractères n'est pas limité aux lettres minuscules. La logique reste un balayage en deux passes : la première pour construire la carte des fréquences, la seconde pour identifier le premier caractère dont la fréquence est 1.

import java.util.HashMap;
import java.util.Map;

public class SolutionCaractereUniqueMapFrequence {
    public int rechercherPremierNonRepete(String texte) {
        Map<Character, Integer> frequences = new HashMap<>();

        // Première passe : Calculer la fréquence de chaque caractère
        for (char lettre : texte.toCharArray()) {
            frequences.put(lettre, frequences.getOrDefault(lettre, 0) + 1);
        }

        // Deuxième passe : Parcourir la chaîne pour trouver le premier caractère avec une fréquence de 1
        for (int i = 0; i < texte.length(); i++) {
            if (frequences.get(texte.charAt(i)) == 1) {
                return i;
            }
        }
        return -1;
    }
}

Approche 3 : Utilisation d'une Carte de Hachage pour Suivre les Indices

Cette méthode utilise également une HashMap, mais son but est de stocker l'indice de la première apparition d'un caractère. Si un caractère est rencontré plus d'une fois, son entrée dans la carte est mise à jour avec une valeur spéciale (par exemple, -1) pour indiquer qu'il est répété. Après avoir parcouru toute la chaîne, on itère sur les valeurs de la carte pour trouver le plus petit indice qui n'est pas -1.

import java.util.HashMap;
import java.util.Map;

public class SolutionCaractereUniqueMapIndice {
    public int obtenirPremierUniqueParIndice(String inputString) {
        Map<Character, Integer> premiereOccurrence = new HashMap<>();

        // Première passe : Enregistrer les indices de première apparition ou marquer les répétés
        for (int i = 0; i < inputString.length(); i++) {
            char caractereActuel = inputString.charAt(i);
            if (premiereOccurrence.containsKey(caractereActuel)) {
                premiereOccurrence.put(caractereActuel, -1); // Marquer comme répété
            } else {
                premiereOccurrence.put(caractereActuel, i); // Enregistrer l'indice de première apparition
            }
        }

        // Deuxième passe : Trouver le plus petit indice parmi les caractères uniques
        int indiceMinimumUnique = Integer.MAX_VALUE;
        for (int index : premiereOccurrence.values()) {
            if (index != -1 && index < indiceMinimumUnique) {
                indiceMinimumUnique = index;
            }
        }

        return (indiceMinimumUnique == Integer.MAX_VALUE) ? -1 : indiceMinimumUnique;
    }
}

Approche 4 : Combinaison d'une Carte de Hachage et d'une File d'Attente

Cette solution tire parti des propriétés FIFO (premier entré, premeir sorti) d'une file d'attente pour maintenir l'ordre des caractères potentiellement uniques. Une HashMap est utilisée pour suivre l'état (indice de première apparition ou -1 si répété) de chaque caractère. Lors du parcours de la chaîne, les caractères vus pour la première fois sont ajoutés à la fois à la carte et à la file. Si un caractère est répété, son statut est mis à jour dans la carte, et tous les éléments en tête de la file qui sont désormais marqués comme répétés sont retirés.

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class SolutionMapQueueUnique {

    // Classe interne pour encapsuler un caractère et son indice d'apparition
    private static class ElementCaractere {
        char val;
        int index;

        ElementCaractere(char val, int index) {
            this.val = val;
            this.index = index;
        }
    }

    public int trouverPremierAvecFile(String s) {
        // Map pour stocker l'indice de première apparition d'un caractère ou -1 si répété
        Map<Character, Integer> etatCaracteres = new HashMap<>();
        // File pour maintenir l'ordre des caractères potentiellement uniques
        Queue<ElementCaractere> candidatsUniques = new LinkedList<>();

        for (int i = 0; i < s.length(); i++) {
            char charCourant = s.charAt(i);

            if (!etatCaracteres.containsKey(charCourant)) {
                // Première fois que nous voyons ce caractère, l'ajouter aux candidats
                etatCaracteres.put(charCourant, i);
                candidatsUniques.offer(new ElementCaractere(charCourant, i));
            } else {
                // Caractère répété : mettre à jour son état dans la map à -1
                etatCaracteres.put(charCourant, -1);
                // Retirer de la file tous les candidats en tête qui sont maintenant répétés
                while (!candidatsUniques.isEmpty() && etatCaracteres.get(candidatsUniques.peek().val) == -1) {
                    candidatsUniques.poll();
                }
            }
        }

        // Après avoir traité toute la chaîne, si la file n'est pas vide,
        // le premier élément est le premier caractère unique
        return candidatsUniques.isEmpty() ? -1 : candidatsUniques.peek().index;
    }
}