In der Serie "Named Problems" stelle ich dir klassische, namentlich bekannte Algorithmus-Probleme vor, die seit Jahrzehnten in Ausbildung, Studium und Interviews verwendet werden. Anhand verständlicher Problemstellungen wie FizzBuzz, Türme von Hanoi oder dem Sieb des Eratosthenes lernst du hier, algorithmisch zu denken, Lösungsstrategien zu entwickeln und diese sauber in Java umzusetzen.

Die Look-and-Say Sequence ist eine bekannte Zahlenfolge, bei der jeder neue Wert entsteht, indem du den vorherigen Wert beschreibst. Statt zu rechnen, beobachtest du Zeichen und zählst Gruppen.

Das klingt erstmal ungewöhnlich, ist aber ein super Übungsproblem für Stringverarbeitung und Iteration. Genau das brauchst du oft im Alltag: Texte scannen, Zeichenketten aufbauen, Schleifen sauber steuern.

In diesem Artikel baust du die Folge Schritt für Schritt nach, erst ganz straightforward, dann etwas sauberer und besser wiederverwendbar.

 

Problemstellung

Gegeben ist ein Startwert (meist 1). Jeder nächste Term entsteht, indem du den aktuellen Term von links nach rechts liest und beschreibst, wie viele gleiche Zeichen hintereinander kommen.

  • Du arbeitest auf Strings (z.B. "1211"), nicht auf Zahlenoperatoren.
  • Du zählst zusammenhängende Gruppen gleicher Zeichen.
  • Aus jeder Gruppe entsteht im Ergebnis: Anzahl gefolgt von Zeichen.

Mini-Beispiel (Start: 1, wir erzeugen mehrere Schritte):

  1. 1 wird gelesen als: "eine 1" → 11
  2. 11 wird gelesen als: "zwei 1" → 21
  3. 21 wird gelesen als: "eine 2, eine 1" → 1211
  4. 1211 wird gelesen als: "eine 1, eine 2, zwei 1" → 111221

 

Die Idee dahinter

Das Kernkonzept hier ist: Stringverarbeitung mit Iteration. Du läufst einmal durch den aktuellen String und gruppierst gleiche Zeichen, die direkt nebeneinander stehen.

Du merkst dir dabei zwei Dinge: das aktuelle Zeichen (z.B. '1') und wie oft es hintereinander vorkommt (z.B. 3). Sobald sich das Zeichen ändert, schreibst du count und das Zeichen ins Ergebnis und startest neu.

  • Aus "111" wird "31"
  • Aus "22" wird "22"
  • Aus "1" wird "11"

 

Schritt für Schritt zur Lösung

  1. Starte mit einem String, z.B. "1", und entscheide, wie viele Terme du erzeugen willst.
  2. Gehe den aktuellen String von links nach rechts durch.
  3. Zähle wie lange das aktuelle Zeichen gleich bleibt (Gruppenbildung).
  4. Wenn das Zeichen wechselt: hänge count und das Zeichen ans Ergebnis.
  5. Am Ende nicht vergessen: die letzte Gruppe muss auch ins Ergebnis.
  6. Wiederhole das für die nächste Iteration, bis du genug Terme hast.

 

Java-Implementierung (Variante A: straightforward)

public class LookAndSayStraightforward {
public static void main(String[] args) {
    String start = "1";
    int terms = 6;

    String current = start;
    System.out.println("Term 1: " + current);

    for (int i = 2; i <= terms; i++) {
        current = nextTerm(current);
        System.out.println("Term " + i + ": " + current);
    }
}

private static String nextTerm(String s) {
    StringBuilder result = new StringBuilder();

    char currentChar = s.charAt(0);
    int count = 1;

    for (int i = 1; i < s.length(); i++) {
        char c = s.charAt(i);

        if (c == currentChar) {
            count++;
        } else {
            result.append(count).append(currentChar);
            currentChar = c;
            count = 1;
        }
    }

    result.append(count).append(currentChar);
    return result.toString();
}

}

Diese Variante ist bewusst direkt: eine Methode nextTerm, die genau einen Schritt erzeugt. Der wichtigste Punkt ist das finale append nach der Schleife, weil die letzte Gruppe sonst verloren geht. Mit StringBuilder vermeidest du zudem unnötige String-Verkettungen in der Schleife.

 

Java-Implementierung (Variante B: Alternative oder Verbesserung)

import java.util.ArrayList; import java.util.List;

public class LookAndSayIterativeList {

public static void main(String[] args) {
    List<String> sequence = generate("1", 6);

    for (int i = 0; i < sequence.size(); i++) {
        System.out.println("Term " + (i + 1) + ": " + sequence.get(i));
    }

    System.out.println("Only step example: " + describe("1211"));
}

public static List<String> generate(String start, int terms) {
    if (terms <= 0) {
        return List.of();
    }
    if (start == null || start.isEmpty()) {
        throw new IllegalArgumentException("start must not be null or empty");
    }

    List<String> result = new ArrayList<>(terms);
    String current = start;
    result.add(current);

    for (int i = 1; i < terms; i++) {
        current = describe(current);
        result.add(current);
    }

    return List.copyOf(result);
}

public static String describe(String s) {
    StringBuilder out = new StringBuilder(s.length() * 2);

    int i = 0;
    while (i < s.length()) {
        char ch = s.charAt(i);
        int count = 1;

        int j = i + 1;
        while (j < s.length() && s.charAt(j) == ch) {
            count++;
            j++;
        }

        out.append(count).append(ch);
        i = j;
    }

    return out.toString();
}

}

Hier ist die Logik besser wiederverwendbar: describe macht einen Schritt, generate baut gleich mehrere Terme und liefert eine Liste zurück. Die innere while-Schleife scannt jede Gruppe in einem Zug, und der Index springt direkt weiter. Das ist oft leichter zu lesen, weil du explizit in Gruppen denkst.

 

Beispiel: Eingabe und Ausgabe

  • Eingabe: describe("1") → Output: "11"
  • Eingabe: describe("11") → Output: "21"
  • Eingabe: describe("1211") → Output: "111221"

 

Typische Fehler

  • Letzte Gruppe vergessen: Nach der Schleife wird nicht mehr angehängt, dadurch fehlt das Ende komplett.
  • Off-by-one in der Schleife: Start bei i = 0 und dann s.charAt(i - 1) nutzen, das knallt sofort.
  • Falsches Zurücksetzen des Counters: Beim Zeichenwechsel count nicht auf 1 setzen, dadurch werden Gruppen falsch beschrieben.
  • String-Verkettung in der Schleife: Immer wieder result = result + ... führt schnell zu schlechter Performance; nutze StringBuilder.
  • Leere Eingabe nicht behandelt: s.charAt(0) bei leerem String wirft eine Exception; prüfe null und isEmpty().
  • Zahlen mit Integer-Logik verwechseln: Die Folge arbeitet auf Zeichen, nicht auf mathematischen Werten (z.B. "21" ist "zwei Eins", nicht 21 als Zahl).

 

Fazit

Mit der Look-and-Say Sequence übst du sehr praktisch, wie man Strings sauber scannt, Gruppen erkennt und neue Strings effizient aufbaut. Du hast gesehen, wie du mit Iteration und einem StringBuilder zu einer kompilierbaren Lösung kommst. Außerdem hast du gelernt, warum das letzte append so wichtig ist und wie kleine Hilfsmethoden den Code besser lesbar machen.