## (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 $n$th sequence.

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

Thoughts:
This question is not hard. We can do a iteration through 1 to $n$. Each time we look back and examine the $(n-1)$th sequence, and count the number of different numbers appearing in it.

Code (Java):

```public class Solution {
public String countAndSay(int n) {
String number = "1";
for(int i = 2; i <= n; ++i) {
String newNumber = new String();
for(int j = 0; j < number.length();) {
char current = number.charAt(j);
int count = 0;
while(j < number.length() &&
current == number.charAt(j)) {
count++;
j++;
}
newNumber += "" + count + current;
}
number = newNumber;
}
return number;
}
}

Code (C++):
class Solution {
public:
string countAndSay(int n) {
string number = "1";
for(int i = 2; i <= n; ++i) {
string newNumber;
for(int j = 0; j < number.size();) {
char current = number[j];
int count = 0;
while(current == number[j]) {
j++;
count++;
}
stringstream ss;
ss << count;
string temp;
ss >> temp;
newNumber += temp;
newNumber.push_back(current);
}
number = newNumber;
}
return number;
}
};

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5b2de9cfbf665', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5b2de9cfbf68e',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5b2de9cfbf690',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});

Related
```

1. Ozan Tabak
Jan 05, 2013 @ 08:06:39

Use string builder in java to concenate Strings for better performance.

public class Solution {
public String countAndSay(int n) {

String str = “1”;
StringBuilder strBuilder = new StringBuilder();
for(int s = 0; s < n – 1; s++) {
int len = str.length();
strBuilder.setLength(0);
char lastChar = str.charAt(0);
int charCnt = 1;

for (int i = 1; i < len; i++) {
char currChar = str.charAt(i);
if (lastChar == currChar) {
charCnt++;
}
else {
strBuilder.append(charCnt).append(lastChar);
charCnt = 1;
}
lastChar = currChar;
}
strBuilder.append(charCnt).append(lastChar);
str = strBuilder.toString();
}
return str;
}
}