Count and Say
Medium · Arrays & Hashing · Explanation and code example
Run-Length Description
How it works
Each term describes consecutive runs in the previous term. For a run of three ones, write 31, meaning three occurrences of one. Build the next term from complete runs before replacing the current term.
Steps
- Start from
1. - Count each consecutive run and append its count followed by its character.
- Repeat n - 1 times.
Complexity
- Time: O(S), where S is the sum of the lengths of all generated terms.
- Space: O(L), where L is the longest generated term.
Things to watch for
- The count describes a run, rather than the total frequency of a digit.
- For n = 1, return
1. - Use a list of fragments in Python to avoid repeated copying during construction.
Python code example
class Solution:
def countAndSay(self, n: int) -> str:
term = "1"
for _ in range(n - 1):
parts = []
i = 0
while i < len(term):
j = i + 1
while j < len(term) and term[j] == term[i]:
j += 1
parts.extend((str(j - i), term[i]))
i = j
term = "".join(parts)
return term
C++ code example
class Solution {
public:
string countAndSay(int n) {
string ans = "1";
while (--n > 0) {
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 = std::move(next);
}
return ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.