Code Logo

Count and Say

Published at25 Jul 2026
Created by
Hard 2 views
Like0

The count-and-say sequence is a series of strings where each term describes the previous term using run-length encoding. Starting with "1", each subsequent term reads the previous term by counting consecutive identical digits.

For example: 1 is read as "one 1" → "11". "11" is read as "two 1s" → "21". "21" is read as "one 2, one 1" → "1211". Given n (1-indexed), return the nth term of the sequence.

This problem teaches run-length encoding and iterative sequence generation. It tests your ability to build a string by counting consecutive identical characters and appending the count followed by the character.

The solution starts with "1" and iterates n-1 times. For each iteration, traverse the current string, count consecutive identical digits, and build the next string by appending each count followed by the digit.

Edge cases include n = 1 (return "1"), large n where the string grows exponentially, and ensuring the count is always correct even when digits repeat many times.

Example Input & Output

Example 1
Input
1
Output
"1"
Explanation

Base case

Example 2
Input
4
Output
"1211"
Explanation

4th term of count-and-say

Example 3
Input
3
Output
"21"
Explanation

Third term

Example 4
Input
2
Output
"11"
Explanation

Second term

Example 5
Input
5
Output
"111221"
Explanation

Fifth term

Algorithm Flow

Recommendation Algorithm Flow for Count and Say

Solution Approach

Build the sequence iteratively by counting consecutive identical digits using run-length encoding.

function countAndSay(n)
  result = "1"
  for i = 2 to n
    current = result
    result = ""
    count = 1
    for j = 1 to length(current) - 1
      if current[j] == current[j-1]
        count = count + 1
      else
        result = result + count + current[j-1]
        count = 1
    result = result + count + current[length(current)-1]
  return result

Start with "1". Repeat n-1 times: traverse the current string, counting consecutive same digits. When a change is detected, append the count and the previous digit. After the loop, append the last group. Update result for the next iteration.

Time complexity is O(2^n) in the worst case as the string length grows exponentially. Space complexity is O(2^n) for the result.

Best Answers

java
class Solution {
    public String solution(int n) {
        String s="1";
        for(int i=1;i<n;i++){StringBuilder nxt=new StringBuilder();int c=1;
            for(int j=1;j<=s.length();j++){
                if(j<s.length()&&s.charAt(j)==s.charAt(j-1))c++;
                else{nxt.append(c).append(s.charAt(j-1));c=1;}
            }s=nxt.toString();
        }return s;
    }
}