# 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;
}
}