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

String Backtracking Medium

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 k-th string of this list or return an empty string if there are less than k happy strings of length n.

Input & Output

Example 1 — Basic Case

$ Input: n = 1, k = 3

› Output: c

💡 Note: For n=1, happy strings are: ['a', 'b', 'c']. The 3rd string is 'c'.

Example 2 — Two Characters

$ Input: n = 2, k = 3

› Output: ba

💡 Note: For n=2, happy strings are: ['ab', 'ac', 'ba', 'bc', 'ca', 'cb']. The 3rd string is 'ba'.

Example 3 — k Too Large

$ Input: n = 2, k = 7

› Output:

💡 Note: There are only 6 happy strings of length 2, so k=7 exceeds the count. Return empty string.

Constraints

1 ≤ n ≤ 4
1 ≤ k ≤ 2³¹ - 1

Visualization

Tap to expand

Asked in

f Facebook 3 G Google 2

The key insight is that happy strings follow a pattern where each position has limited choices: 3 for the first character, 2 for each subsequent character (can't repeat the previous). The optimal approach uses mathematical calculation to directly compute the k-th string without generating all possibilities. Time: O(n), Space: O(1).

Common Approaches

✓ Direct k-th String Generation

⏱️ Time: O(k) Space: O(n)

Use backtracking to generate happy strings in lexicographical order, counting as we go, and return immediately when we reach the k-th string without generating all possibilities.

Generate All Happy Strings

⏱️ Time: O(3 × 2^(n-1)) Space: O(3 × 2^(n-1))

Use backtracking to generate all valid happy strings of length n, store them in a list, sort lexicographically, and return the k-th string if it exists.

Mathematical k-th Calculation

⏱️ Time: O(n) Space: O(1)

Calculate the k-th happy string directly using the fact that for each position, we have a fixed number of choices (3 for first position, 2 for remaining positions). Use division and modulo to determine each character.

Direct k-th String Generation — Algorithm Steps

Use backtracking with early termination
Generate strings in lexicographical order (a, b, c)
Count generated strings and return when count equals k

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate in Order

Create strings lexicographically: ab, ac, ba...

Count & Check

Count each generated string

Stop at k-th

Return immediately when count reaches k

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int count = 0;
char result[20];

void backtrack(char* path, int pos, int n, int k) {
    if (strlen(result) > 0) return;
    
    if (pos == n) {
        count++;
        if (count == k) {
            strcpy(result, path);
        }
        return;
    }
    
    char chars[] = {'a', 'b', 'c'};
    for (int i = 0; i < 3; i++) {
        if (pos == 0 || path[pos-1] != chars[i]) {
            path[pos] = chars[i];
            path[pos+1] = '\0';
            backtrack(path, pos + 1, n, k);
        }
    }
}

char* solution(int n, int k) {
    char path[20];
    count = 0;
    strcpy(result, "");
    backtrack(path, 0, n, k);
    return result;
}

int main() {
    int n, k;
    scanf("%d", &n);
    scanf("%d", &k);
    
    char* res = solution(n, k);
    printf("%s\n", res);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k)

Generate strings until we reach the k-th one

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth equals string length

✓ Linear Space

23.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Direct k-th String Generation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler