The k th lexicographical string of all happy strings of length n

String Backtracking

85.3% acceptance

Feb 25, 2026

1533

A happy string is a string that: consists only of letters of the set ['a', 'b', 'c']. s[i] != s[i + 1] for all values of i from 1 to s.length - 1 (string is 1-indexed). For example, strings "abc", "ac", "b" and "abcbabcbcb" are all happy strings and strings "aa", "baa" and "ababbc" are not happy strings. Given two integers n and k, consider a list of all happy strings of length n sorted in lexicographical order. Return the kth string of this list or return an empty string if there are less than k happy strings of length n.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn get_happy_string(n: i32, k: i32) -> String {
    let n = n as usize;
    let mut result = String::new();
    let mut count = 0i32;
    fn backtrack(cur: &mut String, n: usize, k: i32, count: &mut i32, result: &mut String) {
      if cur.len() == n {
        *count += 1;
        if *count == k {
          *result = cur.clone();
        }
        return;
      }
      for c in ['a', 'b', 'c'] {
        if cur.chars().last().map_or(true, |last| last != c) {
          cur.push(c);
          backtrack(cur, n, k, count, result);
          cur.pop();
          if !result.is_empty() { return; }
        }
      }
    }
    backtrack(&mut String::new(), n, k, &mut count, &mut result);
    result
  }
}