☕ DSA Java Articles

Topics › Strings › Hard String Problems

Count and say

Hard TUF ID 982 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

The count-and-say sequence is a sequence of digit strings. The first term is "1". Every later term is produced by reading the previous term aloud: split it into maximal runs of equal digits, and for each run, from left to right, write the length of the run followed by the digit. Given n ≥ 1, return the n-th term.

Constraints: 1 ≤ n ≤ 30.

The first terms are:

1:  1
2:  11            // "one 1"
3:  21            // "two 1s"
4:  1211          // "one 2, one 1"
5:  111221        // "one 1, one 2, two 1s"
6:  312211        // "three 1s, two 2s, one 1"
7:  13112221
8:  1113213211

Example 1

n = 4
answer = "1211"     // term 3 is "21": one 2, then one 1

Example 2

n = 1
answer = "1"        // the seed itself; nothing is read aloud

The core operation: run-length encoding

There is no shortcut formula for the n-th term, so every solution generates the terms one after another. The real work is one step: turning a string into its “spoken” form. That step is run-length encoding: walk through the string, measure each block of equal characters, and emit count then character.

Take "111221". Its runs are 111, 22, 1, so the next term is "3" + "1" then "2" + "2" then "1" + "1", which is "312211".

Two observations shape the code:

Both approaches below perform this step n - 1 times. They differ in how they build strings, and that turns out to matter.

Approach 1: Brute force, recursion with string concatenation

Intuition. The definition is recursive: term n is the spoken form of term n - 1. So compute term n - 1 recursively, then scan it run by run, gluing the pieces onto a result String with +. This mirrors the definition word for word.

The hidden cost is that Java strings are immutable. result = result + ... allocates a new string and copies everything built so far, so building a string of length L piece by piece costs O(L^2) character copies.

Algorithm.

  1. If n == 1, return "1".
  2. Compute prev, the term for n - 1.
  3. Starting at i = 0, advance j while prev[j] == prev[i]. The run has length j - i.
  4. Append the length and the digit to result, set i = j, and repeat until the end.
static String bruteForce(int n) {
    if (n == 1) return "1";
    String prev = bruteForce(n - 1);
    String result = "";
    int i = 0;
    while (i < prev.length()) {
        int j = i;
        while (j < prev.length() && prev.charAt(j) == prev.charAt(i)) j++;
        result = result + (j - i) + prev.charAt(i);   // count of the run, then its digit
        i = j;
    }
    return result;
}

Complexity. Let L_k be the length of term k. Step k makes up to L_k concatenations, each copying up to L_k characters, so time is O(L_k^2) per step and O(L_n^2) overall in the worst case. Space O(L_n) for the strings plus O(n) recursion depth.

How big is L_n? Conway proved that the length grows by a factor of about 1.3036 per term, so it is exponential in n. Term 30 already has 4462 characters, which is why the problem caps n at 30.

Approach 2: Optimal, iteration with a StringBuilder

Intuition. Keep the same idea but remove both overheads. A loop from 2 to n replaces the recursion, and a StringBuilder replaces repeated concatenation: appending to it is amortised O(1), so building each term costs time proportional to its length.

The scanning loop is written so the “run ended” logic lives in one place. Index i runs from 1 to cur.length() inclusive. If cur[i] exists and equals cur[i - 1], the run continues and the count grows. Otherwise the run ending at i - 1 is flushed. Letting i reach cur.length() is what flushes the final run without a separate statement after the loop.

Algorithm.

  1. Set cur = "1".
  2. Repeat for step = 2 .. n:
    • Set count = 1 and scan i = 1 .. len.
    • If i < len and cur[i] == cur[i - 1], increment count.
    • Otherwise append count and cur[i - 1] to next, and reset count = 1.
    • Set cur = next.
  3. Return cur.
static String optimal(int n) {
    String cur = "1";
    for (int step = 2; step <= n; step++) {
        StringBuilder next = new StringBuilder();
        int count = 1;
        for (int i = 1; i <= cur.length(); i++) {
            if (i < cur.length() && cur.charAt(i) == cur.charAt(i - 1)) {
                count++;                               // the run continues
            } else {
                next.append(count).append(cur.charAt(i - 1));   // the run ended at i - 1
                count = 1;
            }
        }
        cur = next.toString();
    }
    return cur;
}

Dry run from term 5 ("111221") to term 6:

i cur[i - 1] cur[i] action next so far
1 1 1 count = 2  
2 1 1 count = 3  
3 1 2 flush “31” 31
4 2 2 count = 2 31
5 2 1 flush “22” 3122
6 1 end flush “11” 312211

Complexity. Time O(L_2 + L_3 + ... + L_n). Because the lengths grow geometrically, this sum is a constant multiple of L_n, so the total is O(L_n), linear in the size of the answer. No algorithm can beat that, since it must at least write the answer. Space O(L_n) for the current and next terms.

Edge cases and pitfalls