Formations — 1 037 leçons en français

Accueil › Coding & algorithmique › Les problèmes de chaînes qui tombent vraiment

Les problèmes de chaînes qui tombent vraiment

Les chaînes de caractèresdebutant

Cinq problèmes reviennent dans presque tous les entretiens Java. Les connaître libère l'esprit pour la discussion qui suit.

1. Inverser les mots d'une phrase

static String inverserMots(String s) {
    String[] mots = s.strip().split("\\s+");
    Collections.reverse(Arrays.asList(mots));
    return String.join(" ", mots);
}

2. Compression basique — avec la règle qu'on oublie :

static String compresser(String s) {
    StringBuilder sb = new StringBuilder();
    int i = 0;
    while (i < s.length()) {
        char c = s.charAt(i);
        int n = 0;
        while (i < s.length() && s.charAt(i) == c) { i++; n++; }
        sb.append(c).append(n);
    }
    return sb.length() < s.length() ? sb.toString() : s;   // ← la règle oubliée
}

3. Rotation — l'astuce en une ligne :

static boolean estRotation(String a, String b) {
    return a.length() == b.length() && (a + a).contains(b);
}

4. Chaînes isomorphes — deux Maps, pas une :

static boolean isomorphes(String a, String b) {
    if (a.length() != b.length()) return false;
    Map<Character, Character> ab = new HashMap<>(), ba = new HashMap<>();
    for (int i = 0; i < a.length(); i++) {
        char x = a.charAt(i), y = b.charAt(i);
        if (ab.putIfAbsent(x, y) != null && ab.get(x) != y) return false;
        if (ba.putIfAbsent(y, x) != null && ba.get(y) != x) return false;
    }
    return true;
}

5. Caractère intrus — XOR, O(1) en espace :

static char intrus(String a, String b) {   // b = a mélangée + 1 caractère
    int x = 0;
    for (char c : a.toCharArray()) x ^= c;
    for (char c : b.toCharArray()) x ^= c;
    return (char) x;
}

Les termes à connaître

Compression de chaîne

Remplacer les répétitions par un compte : « aaabbc » → « a3b2c1 ». On renvoie l'original si la compression ne gagne rien — la règle qu'on oublie.

Rotation

« erbonjou » est une rotation de « bonjour »… ou pas. L'astuce : b est une rotation de a si et seulement si a.length() == b.length() et (a + a).contains(b).

Inverser les mots

« le chat dort » → « dort chat le ». Se résout avec split + inversion, ou en place sur un char[] pour un O(1) en espace.

Chaîne isomorphe

Deux chaînes où chaque caractère de l'une correspond à un unique caractère de l'autre, de façon cohérente et bijective. Se vérifie avec deux Maps.

Caractère manquant

Trouver ce qui différencie deux chaînes presque identiques : comptage, ou XOR de tous les caractères — l'astuce en O(1) en espace.

Normalisation

Ramener l'entrée à une forme comparable avant de traiter : casse, accents, espaces. À décider explicitement avec l'examinateur.

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.