Count and Say

Problem

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     111221

1 is read off as "one 1" or 11. 11 is read off as "two 1s" or 21. 21 is read off as "one 2, then one 1" or 1211. Given an integer n, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: "1"
Example 2:

Input: 4
Output: "1211"

Solution

Two StringBuilders: O(n^2) time and O(n) space

public class Solution {
    public String countAndSay(int n) {
        StringBuilder cur = new StringBuilder("1");
        StringBuilder prev;
        int count;
        char say;
        while (n-- > 1) {
            prev = cur;
            cur = new StringBuilder();
            count = 1;
            say = prev.charAt(0); //always starts counting from the start 
            for (int i = 1; i < prev.length(); i++) {
                if (prev.charAt(i) != say) {
                    cur.append(count).append(say);
                    count = 1;
                    say = prev.charAt(i);
                } 
                else count++;
            } 
            cur.append(count).append(say);
        }
        return cur.toString();
    }
}

Analysis

The problem looks really complicated
However, as long as we follow its description, everything becomes easier
For each level n > 1, we first set the prev to cur and construct a new cur
Also we need to set up count = 1 and set say to the first character of prev
Then we compare the next element of prev and begin the construction of cur
At the end, we just return cur.toString()