Count And Say

The count-and-say sequence is the sequence of integers beginning as follows:

1, 11, 21, 1211, 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 sequence.

Note: The sequence of integers will be represented as a string.

Example:

if n = 2,
the sequence is 11.

Method:

Construct the sequence one by one by definition..

Solution:

Time: O(2^n) -> the average rate of growth between sequences is (0, 2)
Space: O(2^n)

public class Solution {
    public String countAndSay(int A) {
        String say = "1";
        for (int i = 1; i < A; i ++) {
            char[] arr = say.toCharArray();
            StringBuilder nextSay = new StringBuilder();
            Character prev = null;
            int count = 0;
            for (int j = 0; j < arr.length; j ++) {
                Character c = arr[j];
                if (c == prev) {
                    count ++;
                } else if (prev != null) {
                    nextSay.append("" + count);
                    nextSay.append("" + prev);
                    count = 1;
                } else {
                    count = 1;
                }
                prev = c;
            }
            if (prev != null) {
                nextSay.append("" + count);
                nextSay.append("" + prev);
            }
            say = nextSay.toString();
        }
        return say;
    }
}