Count and Say problem

The problem, simply

The count and say list starts with 1. Every next term is made by reading the term before it out loud, group by group.

1 is read as "one 1", so term 2 is 11. 11 is "two 1s", so term 3 is 21. 21 is "one 2, one 1", so term 4 is 1211. Given n, give back term n as a string.

A story to remember it

Picture it

Examples

Way 1: the simple way

Read each term with a counter, and glue the result together with + on a plain string.

1. Start with cur = "1".
2. Repeat n - 1 times: walk cur, counting how many times the same digit repeats. When the digit changes, glue the count and the digit onto next with next = next + count + digit.
3. cur becomes next.

class Solution {
    public String countAndSay(int n) {
        String cur = "1";
        for (int step = 2; step <= n; step++) {
            String next = "";
            int count = 1;
            for (int i = 1; i <= cur.length(); i++) {
                if (i < cur.length() && cur.charAt(i) == cur.charAt(i - 1)) {
                    count++;                                   // same run goes on
                } else {
                    next = next + count + cur.charAt(i - 1);   // copies next every time
                    count = 1;
                }
            }
            cur = next;
        }
        return cur;
    }
}

How long it takes: Java strings cannot change, so every next + ... builds a brand new string and copies all of next into it. For a term of length L that is about L^2 copying, so O(L^2), where L is the length of the last term. Extra room: the current and next strings, O(L).

Way 2: the clever way

Same reading, two better habits. Use a StringBuilder, which grows in place instead of copying. And read each run with two fingers: i at the start of the run and j sliding right while the digit stays the same. The run length is j - i.

1. Start with cur = "1".
2. For each step, set i = 0. Slide j from i while cur[j] == cur[i]. Append j - i and cur[i]. Set i = j and repeat until the end.
3. cur becomes what you built.

class Solution {
    public String countAndSay(int n) {
        String cur = "1";
        for (int step = 2; step <= n; step++) {
            StringBuilder next = new StringBuilder();
            int i = 0;
            while (i < cur.length()) {
                int j = i;
                while (j < cur.length() && cur.charAt(j) == cur.charAt(i)) j++;  // slide over the run
                next.append(j - i).append(cur.charAt(i));                       // say count, then digit
                i = j;                                                         // next run starts here
            }
            cur = next.toString();
        }
        return cur;
    }
}

How long it takes: each step reads its term once. The terms grow by about 30 percent each time, so all the earlier terms together are only a few times longer than the last one. In total that is O(L), where L is the length of term n. Extra room: O(L) for the strings.

Watch out for

• n = 1 must return "1" without reading anything.
• Append the count as a number, not as a char. append((char) count) would add a strange symbol.
• The terms grow fast. Term 30 already has more than 4000 digits, so never turn them into int or long.

What interviewers ask next

• Which digits can appear? Only 1, 2 and 3. A run of four equal digits would need an earlier term to say the same thing twice in a row, which cannot happen.
• How fast do the terms grow? Each term is about 1.3036 times longer than the one before. This is Conway's constant, and it is a fun fact quant firms like.
• Write the recursive version? countAndSay(n) reads countAndSay(n - 1). Same work, but it keeps n calls on the stack.
• Run length encode a general string, like aaabcc to a3b1c2? The same two finger loop. Compress in place in an array (LeetCode 443) by writing with a third finger.

Remember this

Grown-up words: reading in runs is run length encoding, the two fingers are two pointers, StringBuilder avoids the copying that comes from immutable strings, and the growth rate of about 1.3 is Conway's constant.