Speak-and-count sequence generation

You are in a phone screen with Apple when the interviewer says, "I'm going to read you a sequence, and I want you to figure out the pattern." They say: one. Then: one one. Then: two ones. Then: one two, one one. You realize each term is a description of the previous one, spoken aloud. This is the count-and-say sequence, also known as the "look-and-say" sequence on other platforms. It is a classic string manipulation problem that tests your ability to translate a verbal pattern into clean, iterative code.

TL;DR

Build the nth term iteratively by starting with "1" and applying run-length encoding n-1 times. For each term, scan left to right, count consecutive identical digits, and append the count followed by the digit to a StringBuilder. The key detail is remembering to flush the final group after the loop ends. Time and space are both O(2^n) because the string length grows exponentially.

Why This Problem Matters

The count-and-say problem sits at a sweet spot for interviews. It does not require exotic data structures or advanced algorithms. Instead, it tests whether you can parse a word problem, identify the core operation (run-length encoding), and implement it cleanly with proper loop boundaries. Companies like Apple, Meta, and Akuna Capital use it because it reveals how a candidate handles string building, edge cases, and iterative simulation under time pressure.

Understanding the Sequence

The count-and-say sequence is built on a simple idea: each term describes the previous term using run-length encoding. Starting from "1":

• n=1: "1" (the seed)
• n=2: "11" (one 1)
• n=3: "21" (two 1s)
• n=4: "1211" (one 2, one 1)
• n=5: "111221" (one 1, one 2, two 1s)

Here is how the sequence evolves visually:

Each arrow represents one application of run-length encoding. The string grows with every step, roughly 30% longer each time (governed by Conway's constant, approximately 1.3036).

Run-Length Encoding: The Core Operation

The entire problem reduces to one helper function: given a string, produce its run-length encoded version. You scan from left to right, counting how many times the current character repeats consecutively. When you hit a different character (or reach the end), you write out the count and the character, then start a new group.

Let's trace this on the string "1211" to produce term n=5:

Reading "1211" left to right: one 1, one 2, two 1s. Concatenating the counts and digits gives "111221".

Edge Cases to Consider

1. n=1: Return "1" immediately, no encoding needed
2. n ≤ 0: Return an empty string (defensive guard)
3. Single-character string: The encoding produces exactly two characters (count + digit)
4. Large n: Strings grow exponentially, so use StringBuilder for efficient concatenation

Solution Approach

The algorithm is straightforward:

1. Initialize result = "1" (the first term)
2. Loop n-1 times, replacing result with its run-length encoding each iteration
3. For each encoding pass, walk through the string character by character
4. Track the current character and a running count of consecutive matches
5. When the character changes, append the count and the old character to the output, then reset
6. After the loop, append the final group (this is the step most candidates forget)

Here is the flow of the helper function:

The critical detail is that last "append" after the loop. When you reach the end of the string, you are still holding an unwritten group. Forgetting to flush it is the single most common bug in interviews for this problem.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public String countAndSay(int n) {
    if (n <= 0) {
      return "";
    }

    String result = "1";
    for (int i = 1; i < n; i++) {
      result = getNextSequence(result);
    }
    return result;
  }

  private String getNextSequence(String sequence) {
    StringBuilder nextSequence = new StringBuilder();
    int count = 1;
    char currentChar = sequence.charAt(0);

    for (int i = 1; i < sequence.length(); i++) {
      if (sequence.charAt(i) == currentChar) {
        count++;
      } else {
        nextSequence.append(count).append(currentChar);
        currentChar = sequence.charAt(i);
        count = 1;
      }
    }
    // Flush the last group
    nextSequence.append(count).append(currentChar);

    return nextSequence.toString();
  }
}

Let's trace through countAndSay(4) step by step:

Iteration 1 (i=1): Encode "1". One 1, so result becomes "11".

Iteration 2 (i=2): Encode "11". Two 1s, so result becomes "21".

Iteration 3 (i=3): Encode "21". One 2, one 1, so result becomes "1211".

The method returns "1211", which matches the expected output.

Why StringBuilder?

In Java, strings are immutable. Every += operation creates a new String object and copies all existing characters. For a string of length L, this makes each encoding pass O(L^2). StringBuilder uses a resizable buffer and appends in amortized O(1), keeping each pass O(L).

For n=30, the string is over 5,000 characters long. By n=50, it exceeds 1.3 million characters. Without StringBuilder, you would see noticeable slowdowns starting around n=25.

Complexity Analysis

Time Complexity: O(2^n)

Each encoding pass processes a string whose length grows by roughly 30% per step. The total work across all n iterations is dominated by the last few terms, where the string is longest. Because the string length grows exponentially (bounded by Conway's constant ~1.3036), the overall time complexity is O(2^n). In practice, the base is closer to 1.3 than 2, but the exponential nature means even small increases in n produce significantly longer strings.

Space Complexity: O(2^n)

You need to store the current term and the next term simultaneously during each encoding pass. The longest term (at step n) dominates the space usage, and its length grows exponentially.

Why Not Recursive?

A recursive approach would call countAndSay(n-1) to get the previous term, then encode it. This works but adds O(n) call stack frames on top of the already exponential string storage. Since the iterative approach is equally simple and avoids the stack overhead, it is the standard choice in interviews.

Common Pitfalls

Having seen this problem in many interviews, here are the mistakes that trip people up:

1. Forgetting the final group: The inner loop only appends when it encounters a different character. The last group of identical characters is never followed by a different one, so you must append it after the loop ends.

   // After the for loop, this line is essential:
   nextSequence.append(count).append(currentChar);
   

2. Using string concatenation in a loop: Building the result with result += count + currentChar creates a new string on every append. This is fine for small n but causes O(L^2) behavior per pass for large values.

3. Off-by-one on loop start: The inner loop should start at index 1 (not 0) since currentChar is initialized to the first character. Starting at 0 would double-count the first character.

4. Not handling n=1: If you skip the guard and go straight into the loop with i = 1; i < n, it works for n=1 since the loop body never executes. But explicitly handling n <= 0 as an edge case shows defensive coding.

Interview Tips

When you encounter this problem in an interview:

1. Restate the pattern in your own words: "Each term is the run-length encoding of the previous term, starting from '1'." This confirms your understanding.

2. Walk through a small example: Trace n=1 through n=4 on paper. This builds confidence and catches misunderstandings before you write code.

3. Name the helper function clearly: Calling it getNextSequence or runLengthEncode signals that you understand the decomposition.

4. Mention StringBuilder proactively: Saying "I'll use StringBuilder to avoid quadratic string concatenation" shows awareness of performance.

5. Test with edge cases: After coding, trace through n=1 (base case) and n=2 (single encoding step). If time permits, also trace n=5 to verify multi-digit counts.

6. Discuss the exponential growth: Mentioning Conway's constant or the exponential nature of the sequence shows depth. Not every candidate knows this, so it sets you apart.

Related Problems

Once you are comfortable with count-and-say, try these related string and simulation problems:

• Simple sorted string compression (run-length encoding in a simpler setting)
• Recover IP addresses (string parsing with backtracking)
• Zigzag string transformation (iterative string building with a pattern)

Practice on Firecode

The count-and-say sequence is a great example of a problem that looks tricky at first but becomes straightforward once you identify the core operation. Consistent practice with problems like this builds the pattern recognition that separates strong candidates from the rest. This problem and thousands of others are available on Firecode, where over 50,000 users have prepared for technical interviews and landed six and seven-figure roles at top tech companies.

Solutions in Other Languages

Python

class Solution:
    def count_and_say(self, n: int) -> str:
        def next_sequence(s: str) -> str:
            result = []
            i = 0
            while i < len(s):
                count = 1
                while i + 1 < len(s) and s[i] == s[i + 1]:
                    i += 1
                    count += 1
                result.append(f"{count}{s[i]}")
                i += 1
            return ''.join(result)

        current = "1"
        for _ in range(1, n):
            current = next_sequence(current)
        return current

JavaScript

class Solution {
  countAndSay(n) {
    const runLengthEncode = (s) => {
      let result = '';
      let count = 1;
      for (let i = 1; i <= s.length; i++) {
        if (s[i] === s[i - 1]) {
          count++;
        } else {
          result += count.toString() + s[i - 1];
          count = 1;
        }
      }
      return result;
    };

    let current = "1";
    for (let i = 1; i < n; i++) {
      current = runLengthEncode(current);
    }
    return current;
  }
}

TypeScript

class Solution {
  countAndSay(n: number): string {
    const runLengthEncode = (s: string): string => {
      let result = '';
      let count = 1;
      for (let i = 1; i <= s.length; i++) {
        if (s[i] === s[i - 1]) {
          count++;
        } else {
          result += count.toString() + s[i - 1];
          count = 1;
        }
      }
      return result;
    };

    let current = "1";
    for (let i = 1; i < n; i++) {
      current = runLengthEncode(current);
    }
    return current;
  }
}

C++

#include <string>

class Solution {
public:
  std::string countAndSay(int n) {
    if (n == 1) return "1";

    std::string current = "1";
    for (int i = 2; i <= n; ++i) {
      current = getNextSequence(current);
    }
    return current;
  }

private:
  std::string getNextSequence(const std::string& sequence) {
    std::string nextSequence;
    int count = 1;
    char currentChar = sequence[0];

    for (size_t i = 1; i < sequence.size(); ++i) {
      if (sequence[i] == currentChar) {
        ++count;
      } else {
        nextSequence += std::to_string(count) + currentChar;
        currentChar = sequence[i];
        count = 1;
      }
    }
    nextSequence += std::to_string(count) + currentChar;
    return nextSequence;
  }
};

Go

package solution

import "strconv"

func (s *Solution) CountAndSay(n int) string {
    if n <= 0 {
        return ""
    }

    result := "1"
    for i := 1; i < n; i++ {
        result = nextSequence(result)
    }
    return result
}

func nextSequence(s string) string {
    var result string
    count := 0
    currentChar := s[0]

    for i := 0; i < len(s); i++ {
        if s[i] == currentChar {
            count++
        } else {
            result += strconv.Itoa(count) + string(currentChar)
            currentChar = s[i]
            count = 1
        }
    }
    result += strconv.Itoa(count) + string(currentChar)
    return result
}

Scala

class Solution {
  def countAndSay(n: Int): String = {
    def runLengthEncode(s: String): String = {
      val sb = new StringBuilder
      var i = 0
      while (i < s.length) {
        val char = s(i)
        var count = 0
        while (i < s.length && s(i) == char) {
          count += 1
          i += 1
        }
        sb.append(count).append(char)
      }
      sb.toString()
    }

    var result = "1"
    for (_ <- 1 until n) {
      result = runLengthEncode(result)
    }
    result
  }
}

Kotlin

class Solution {
    fun countAndSay(n: Int): String {
        if (n <= 0) return ""

        var result = "1"
        for (i in 1 until n) {
            result = getNextSequence(result)
        }
        return result
    }

    private fun getNextSequence(sequence: String): String {
        val nextSequence = StringBuilder()
        var count = 1
        var currentChar = sequence[0]

        for (i in 1 until sequence.length) {
            if (sequence[i] == currentChar) {
                count++
            } else {
                nextSequence.append(count).append(currentChar)
                currentChar = sequence[i]
                count = 1
            }
        }
        nextSequence.append(count).append(currentChar)
        return nextSequence.toString()
    }
}

Swift

import Foundation

class Solution {
    func countAndSay(_ n: Int) -> String {
        if n <= 0 { return "" }

        var result = "1"
        for _ in 1..<n {
            result = getNextSequence(result)
        }
        return result
    }

    private func getNextSequence(_ sequence: String) -> String {
        var nextSequence = ""
        var count = 1
        var currentChar = sequence[sequence.startIndex]

        var index = sequence.index(after: sequence.startIndex)
        while index < sequence.endIndex {
            if sequence[index] == currentChar {
                count += 1
            } else {
                nextSequence += "\(count)\(currentChar)"
                currentChar = sequence[index]
                count = 1
            }
            index = sequence.index(after: index)
        }
        nextSequence += "\(count)\(currentChar)"
        return nextSequence
    }
}

Rust

pub struct Solution;

impl Solution {
    pub fn count_and_say(&self, n: i32) -> String {
        if n <= 0 {
            return String::new();
        }

        let mut result = String::from("1");
        for _ in 1..n {
            result = Self::get_next_sequence(&result);
        }
        result
    }

    fn get_next_sequence(sequence: &str) -> String {
        let mut next_sequence = String::new();
        let mut count = 1;
        let chars: Vec<char> = sequence.chars().collect();
        let mut current_char = chars[0];

        for i in 1..chars.len() {
            if chars[i] == current_char {
                count += 1;
            } else {
                next_sequence.push_str(&format!("{}{}", count, current_char));
                current_char = chars[i];
                count = 1;
            }
        }
        next_sequence.push_str(&format!("{}{}", count, current_char));
        next_sequence
    }
}

Ruby

class Solution
  def count_and_say(n)
    return '' if n <= 0

    result = '1'
    (1...n).each do
      result = get_next_sequence(result)
    end
    result
  end

  def get_next_sequence(sequence)
    next_sequence = ''
    count = 1
    current_char = sequence[0]

    (1...sequence.length).each do |i|
      if sequence[i] == current_char
        count += 1
      else
        next_sequence += "#{count}#{current_char}"
        current_char = sequence[i]
        count = 1
      end
    end
    next_sequence += "#{count}#{current_char}"
    next_sequence
  end
end

C#

using System.Text;

public class Solution {
    public string CountAndSay(int n) {
        if (n <= 0) return "";

        var result = "1";
        for (int i = 1; i < n; i++) {
            result = GetNextSequence(result);
        }
        return result;
    }

    private string GetNextSequence(string sequence) {
        var nextSequence = new StringBuilder();
        int count = 1;
        char currentChar = sequence[0];

        for (int i = 1; i < sequence.Length; i++) {
            if (sequence[i] == currentChar) {
                count++;
            } else {
                nextSequence.Append(count).Append(currentChar);
                currentChar = sequence[i];
                count = 1;
            }
        }
        nextSequence.Append(count).Append(currentChar);
        return nextSequence.ToString();
    }
}

Dart

class Solution {
  String countAndSay(int n) {
    if (n <= 0) return "";

    String result = "1";
    for (int i = 1; i < n; i++) {
      result = _getNextSequence(result);
    }
    return result;
  }

  String _getNextSequence(String sequence) {
    StringBuffer nextSequence = StringBuffer();
    int count = 1;
    String currentChar = sequence[0];

    for (int i = 1; i < sequence.length; i++) {
      if (sequence[i] == currentChar) {
        count++;
      } else {
        nextSequence.write('$count$currentChar');
        currentChar = sequence[i];
        count = 1;
      }
    }
    nextSequence.write('$count$currentChar');
    return nextSequence.toString();
  }
}

PHP

class Solution {
    public function countAndSay(int $n): string {
        if ($n <= 0) return "";

        $result = "1";
        for ($i = 1; $i < $n; $i++) {
            $result = $this->getNextSequence($result);
        }
        return $result;
    }

    private function getNextSequence(string $sequence): string {
        $nextSequence = "";
        $count = 1;
        $currentChar = $sequence[0];

        for ($i = 1; $i < strlen($sequence); $i++) {
            if ($sequence[$i] === $currentChar) {
                $count++;
            } else {
                $nextSequence .= $count . $currentChar;
                $currentChar = $sequence[$i];
                $count = 1;
            }
        }
        $nextSequence .= $count . $currentChar;
        return $nextSequence;
    }
}