## Count and Say

• Time:O(|\texttt{ans}|)
• Space:O(|\texttt{ans}|)

## C++

``````class Solution {
public:
string countAndSay(int n) {
string ans = "1";

while (--n) {
string next;
for (int i = 0; i < ans.length(); ++i) {
int count = 1;
while (i + 1 < ans.length() && ans[i] == ans[i + 1]) {
++count;
++i;
}
next += to_string(count) + ans[i];
}
ans = move(next);
}

return ans;
}
};
``````

## JAVA

``````class Solution {
public String countAndSay(int n) {
StringBuilder sb = new StringBuilder("1");

while (--n > 0) {
StringBuilder next = new StringBuilder();
for (int i = 0; i < sb.length(); ++i) {
int count = 1;
while (i + 1 < sb.length() && sb.charAt(i) == sb.charAt(i + 1)) {
++count;
++i;
}
next.append(count).append(sb.charAt(i));
}
sb = next;
}

return sb.toString();
}
}
``````

## Python

``````class Solution:
def countAndSay(self, n: int) -> str:
ans = '1'

for _ in range(n - 1):
nxt = ''
i = 0
while i < len(ans):
count = 1
while i + 1 < len(ans) and ans[i] == ans[i + 1]:
count += 1
i += 1
nxt += str(count) + ans[i]
i += 1
ans = nxt

return ans
``````