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 laHashMap: 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) + 1fait 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.
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.