The k-th Lexicographical String of All Happy Strings of Length n

medium backtracking counting

Problem

A happy string uses only the letters a, b, c and never repeats a letter in two adjacent positions. Imagine every happy string of length n written out in alphabetical (lexicographical) order.

Given n and k (1 ≤ n ≤ 10, 1 ≤ k ≤ 100), return the k-th string in that sorted list, or the empty string if the list contains fewer than k strings.

Inputn = 3, k = 9

Output"cab"

The 12 happy strings of length 3 are aba, abc, aca, acb, bab, bac, bca, bcb, cab, cac, cba, cbc — the 9th is "cab".

n (string length, 1–7)

k (1-based rank, 1–100)

def get_happy_string(n, k):
    total = 3 * (1 << (n - 1))      # happy strings of length n
    if k > total:
        return ""                       # list is too short
    k -= 1                              # 0-based leaf index
    res = []
    for i in range(n):
        block = 1 << (n - 1 - i)    # leaves under each choice here
        for c in "abc":
            if res and res[-1] == c:
                continue                # would repeat previous letter
            if k < block:
                res.append(c)           # target leaf is in this subtree
                break
            k -= block                  # skip this whole subtree
    return "".join(res)

function getHappyString(n, k) {
  const total = 3 * (1 << (n - 1)); // happy strings of length n
  if (k > total) return "";
  k -= 1;                              // 0-based leaf index
  let res = "";
  for (let i = 0; i < n; i++) {
    const block = 1 << (n - 1 - i); // leaves under each choice here
    for (const c of "abc") {
      if (res.endsWith(c)) continue;        // would repeat previous letter
      if (k < block) { res += c; break; }  // target is in this subtree
      k -= block;                           // skip this whole subtree
    }
  }
  return res;
}

String getHappyString(int n, int k) {
    int total = 3 * (1 << (n - 1));      // happy strings of length n
    if (k > total) return "";
    k -= 1;                                  // 0-based leaf index
    StringBuilder res = new StringBuilder();
    for (int i = 0; i < n; i++) {
        int block = 1 << (n - 1 - i);    // leaves under each choice here
        for (char c = 'a'; c <= 'c'; c++) {
            if (i > 0 && res.charAt(i - 1) == c) continue;
            if (k < block) { res.append(c); break; }
            k -= block;                      // skip this whole subtree
        }
    }
    return res.toString();
}

string getHappyString(int n, int k) {
    int total = 3 * (1 << (n - 1));      // happy strings of length n
    if (k > total) return "";
    k -= 1;                                  // 0-based leaf index
    string res;
    for (int i = 0; i < n; i++) {
        int block = 1 << (n - 1 - i);    // leaves under each choice here
        for (char c = 'a'; c <= 'c'; c++) {
            if (!res.empty() && res.back() == c) continue;
            if (k < block) { res += c; break; }
            k -= block;                      // skip this whole subtree
        }
    }
    return res;
}

Explanation

The key insight is that we can count instead of enumerate. The first position of a happy string has 3 choices (a, b, c) and every later position has exactly 2 (anything except the previous letter), so there are 3 · 2^(n−1) happy strings in total — and once a prefix is fixed through position i, exactly block = 2^(n−1−i) strings hang below it.

Picture the choice tree a backtracking solution would explore: because we always try letters in a → b → c order, its leaves are exactly the happy strings already in lexicographic order. Finding the k-th string means walking to the k-th leaf. At each position we ask: does the 0-based remaining index k0 = k − 1 fall inside the first allowed letter's block of 2^(n−1−i) leaves? If yes, commit that letter and descend; if not, subtract the block and test the next letter. Letters equal to the previous one are skipped outright — they root no leaves at all.

Walking the default example n = 3, k = 9: there are 12 strings and k0 = 8. At position 0 each letter covers 4 leaves, so we skip a (k0 → 4), skip b (k0 → 0), and descend into c. At position 1 the block is 2 and a is allowed with k0 = 0 < 2, so we take a. At position 2 the block is 1: a is banned (it equals the previous letter), and b wins with k0 = 0 < 1. The answer is "cab".

This is backtracking with the recursion replaced by arithmetic: instead of actually visiting the 2^(n−1−i) leaves of a rejected subtree one by one, we fast-forward past them with a single subtraction. A plain DFS that emits happy strings until the k-th appears also passes the small constraints (k ≤ 100), but the counting version never enters a dead branch.

If k > 3 · 2^(n−1) the requested string does not exist and we return "" immediately. Otherwise each of the n positions examines at most 3 candidate letters and does constant work per candidate, so the whole walk is linear in n, and the only storage is the answer being built.

Time: O(n) Space: O(n)