# 38. Count and Say¶

• Time: $O(|\texttt{ans}|)$
• Space: $O(|\texttt{ans}|)$
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 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; } };
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 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(); } }
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 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