38. Count and Say

Time: O(n·|output|)

Space: O(|output|)

Intuition

Each term describes the previous term using run-length encoding: count consecutive identical digits and say "count digit". Build each string from the previous one iteratively.

Algorithm

1Start with s = "1".
2Repeat n-1 times: scan s, group consecutive identical characters, build the next string as "count + char" for each group.
3Return s.

Example Walkthrough

Input: n = 4

1.n=1: "1"
2.n=2: one 1 -> "11"
3.n=3: two 1s -> "21"
4.n=4: one 2, one 1 -> "1211"

Output: "1211"

Common Pitfalls

•Use a StringBuilder for O(n) string building - repeated string concatenation is O(n^2).

38.cs

// Approach: Iteratively build each term by applying run-length encoding
// to the previous term (count consecutive identical digits).
// Time: O(n·|output|) Space: O(|output|)

public class Solution
{
    public string CountAndSay(int n)
    {
        string val = "1";

        for (int i = 1; i < n; i++)
        {
            char c = val[0];
            StringBuilder s = new StringBuilder();
            int cnt = 1;

            for (int j = 1; j < val.Length; j++)
            {
                if (c != val[j])
                {
                    s.Append(cnt);
                    s.Append(c);
                    cnt = 0;
                    c = val[j];
                }
                cnt++;
            }
            s.Append(cnt);
            s.Append(c);
            val = s.ToString();
        }

        return val;
    }
}

Was this solution helpful?