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

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

Understanding the Visualization

Input

n=2, k=3 (find 3rd happy string of length 2)

Happy Strings

Generate: ab, ac, ba, bc, ca, cb (6 total)

Output

Return 3rd string: "ba"

Key Takeaway

🎯 Key Insight: Happy strings have exactly 3 × 2^(n-1) possibilities, allowing direct mathematical calculation

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

Approach	Time	Space	Notes
✓ Generate All Happy Strings	O(3 × 2^(n-1))	O(3 × 2^(n-1))	Generate all possible happy strings, sort them, and return the k-th one
Direct k-th String Generation	O(k)	O(n)	Generate strings in lexicographical order and stop at the k-th one
Mathematical k-th Calculation	O(n)	O(1)	Use mathematical calculation to directly find the k-th happy string

Generate All Happy Strings — Algorithm Steps

Generate all happy strings using backtracking
Sort the list lexicographically
Return k-th string or empty string if k exceeds count

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate All

Use backtracking to create all valid strings

Sort

Sort all strings lexicographically

Select k-th

Return the k-th string from sorted list

Code -

solution.c — C

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

#define MAX_STRINGS 1000000

char strings[MAX_STRINGS][20];
int count = 0;

void backtrack(char* path, int pos, int n) {
    if (pos == n) {
        strcpy(strings[count], path);
        count++;
        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);
        }
    }
}

int compare(const void* a, const void* b) {
    return strcmp((char*)a, (char*)b);
}

char* solution(int n, int k) {
    char path[20];
    count = 0;
    backtrack(path, 0, n);
    
    qsort(strings, count, sizeof(strings[0]), compare);
    
    if (k <= count) {
        static char result[20];
        strcpy(result, strings[k-1]);
        return result;
    }
    
    static char empty[] = "";
    return empty;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(3 × 2^(n-1))

Generate all happy strings: 3 choices for first char, 2 for each remaining position

✓ Linear Growth

Space Complexity

O(3 × 2^(n-1))

Store all generated happy strings in memory

⚡ Linearithmic 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Generate All Happy Strings — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler