Formations — 1 037 leçons en français

Accueil › Coding & algorithmique › Comptage de fréquences : anagrammes et caractères uniques

Comptage de fréquences : anagrammes et caractères uniques

Les chaînes de caractèresdebutant

Compter les occurrences résout une famille entière d'exercices : anagrammes, premier caractère unique, caractères en trop, chaînes permutables.

Deux structures, selon l'alphabet :

// Alphabet ouvert (mots, Unicode, objets) → HashMap
Map<Character, Integer> f = new HashMap<>();
for (char c : s.toCharArray()) f.merge(c, 1, Integer::sum);

// Alphabet petit et connu (26 lettres, 128 ASCII) → tableau
int[] f = new int[26];
for (char c : s.toCharArray()) f[c - 'a']++;

c - 'a' convertit une lettre minuscule en index 0-25 : l'idiome à connaître.

L'anagramme se vérifie en un passage aller-retour :

static boolean anagrammes(String a, String b) {
    if (a.length() != b.length()) return false;      // sortie anticipée
    int[] f = new int[26];
    for (int i = 0; i < a.length(); i++) {
        f[a.charAt(i) - 'a']++;
        f[b.charAt(i) - 'a']--;
    }
    for (int n : f) if (n != 0) return false;
    return true;
}

Une seule boucle incrémente pour la première chaîne et décrémente pour la seconde : si tout revient à zéro, les chaînes sont anagrammes. O(n) en temps, O(1) en espace.

Le premier caractère unique demande deux passages : un pour compter, un pour retrouver l'ordre d'apparition.

Les termes à connaître

Table de fréquences

Une structure qui associe chaque élément à son nombre d'occurrences. C'est le motif le plus réutilisé des exercices d'entretien.

Tableau de comptage

Quand l'alphabet est petit et connu (26 lettres, 128 codes ASCII), un int[] remplace la HashMap : accès direct par index, aucune allocation d'objet.

Anagramme

Deux chaînes formées des mêmes caractères, dans un ordre différent. Se vérifie par comparaison de leurs tables de fréquences, en O(n).

Signature canonique

Une représentation identique pour tous les éléments d'un même groupe : les lettres triées, ou le vecteur de comptages sérialisé. Sert de clé pour regrouper des anagrammes.

merge / getOrDefault

map.merge(c, 1, Integer::sum) incrémente en une ligne. getOrDefault(c, 0) + 1 fait la même chose de façon plus explicite.

Sortie anticipée

Renvoyer dès que la réponse est connue — première différence de longueur, premier caractère en trop. Ne change pas la complexité, mais montre la rigueur.

Lire l'explication détaillée et faire le quiz →

Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.