Count and say

String

62.4% acceptance

Jan 12, 2026

5072

9048

The count-and-say sequence is a sequence of digit strings defined by the recursive formula: countAndSay(1) = "1" countAndSay(n) is the run-length encoding of countAndSay(n - 1). Run-length encoding (RLE) is a string compression method that works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string "3322251" we replace "33" with "23", replace "222" with "32", replace "5" with "15" and replace "1" with "11". Thus the compressed string becomes "23321511". Given a positive integer n, return the nth element of the count-and-say sequence.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_and_say(n: i32) -> String {
    let mut result = String::from("1");
    
    for _ in 1..n {
      result = Self::rle(&result);
    }
    
    result
  }
  
  fn rle(s: &str) -> String {
    let mut result = String::new();
    let chars: Vec<char> = s.chars().collect();
    let mut i = 0;
    
    while i < chars.len() {
      let current = chars[i];
      let mut count = 1;
      
      while i + count < chars.len() && chars[i + count] == current {
        count += 1;
      }
      
      result.push_str(&count.to_string());
      result.push(current);
      i += count;
    }
    
    result
  }
}