Count and Say

medium string

Problem

The count-and-say sequence starts with "1". Each subsequent term is generated by reading the previous term and saying it: count consecutive equal digits and write "count digit". Return the n-th term.

Inputn = 4

Output"1211"

1 → 11 → 21 → 1211.

def count_and_say(n):
    s = "1"
    for _ in range(n - 1):
        out, i = [], 0
        while i < len(s):
            j = i
            while j < len(s) and s[j] == s[i]:
                j += 1
            out.append(str(j - i) + s[i])
            i = j
        s = "".join(out)
    return s

function countAndSay(n) {
  let s = "1";
  for (let k = 1; k < n; k++) {
    let out = "", i = 0;
    while (i < s.length) {
      let j = i;
      while (j < s.length && s[j] === s[i]) j++;
      out += (j - i) + s[i];
      i = j;
    }
    s = out;
  }
  return s;
}

class Solution {
    public String countAndSay(int n) {
        String s = "1";
        for (int k = 1; k < n; k++) {
            StringBuilder sb = new StringBuilder();
            int i = 0;
            while (i < s.length()) {
                int j = i;
                while (j < s.length() && s.charAt(j) == s.charAt(i)) j++;
                sb.append(j - i).append(s.charAt(i));
                i = j;
            }
            s = sb.toString();
        }
        return s;
    }
}

string countAndSay(int n) {
    string s = "1";
    for (int k = 1; k < n; k++) {
        string out;
        int i = 0;
        while (i < (int)s.size()) {
            int j = i;
            while (j < (int)s.size() && s[j] == s[i]) j++;
            out += to_string(j - i) + s[i];
            i = j;
        }
        s = out;
    }
    return s;
}

Explanation

The sequence is built by describing the previous term out loud. To go from one term to the next, you read it as groups of identical digits and write "how many, then which digit" for each group.

We start with s = "1" and repeat the build step n - 1 times so we land on the n-th term. Each build step scans the current string with two pointers: i marks the start of a group and j runs forward as long as s[j] equals s[i].

When j stops, the group length is j - i, so we append str(j - i) + s[i] to the new string and jump i to j to start the next group. After the whole scan, the freshly built string becomes s for the next round.

This grouping of consecutive equal digits is the heart of "count and say" — you literally count a run and then say it.

Example for n = 4: "1" → one 1 → "11" → two 1s → "21" → one 2 then one 1 → "1211".

Time: O(n · |sₙ|) Space: O(|sₙ|)