Count and Say

Share

Generate the nth term of the count-and-say sequence.

Example 1
Input: n=1 → Output: "1"
Example 2
Input: n=4 → Output: "1211". 1 → 11 → 21 → 1211

Solution Approach

Build each term by reading off consecutive groups of same digits from previous term.

  • Start with "1"
  • For each step 1..n-1: scan current string for runs of same digit
  • Append count then digit to next string
  • Repeat n-1 times
Java
public String countAndSay(int n) {
    String s = "1";
    for (int i = 1; i < n; i++) {
        StringBuilder sb = new StringBuilder();
        int j = 0;
        while (j < s.length()) {
            char c = s.charAt(j);
            int count = 0;
            while (j < s.length() && s.charAt(j) == c) { j++; count++; }
            sb.append(count).append(c);
        }
        s = sb.toString();
    }
    return s;
}
  • Time Complexity: O(n * 2^n)
  • Space Complexity: O(2^n)