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

/**
 * Problem: LeetCode 1415 - The k-th Lexicographical String of All Happy Strings of Length n
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
class Solution {
    public String getHappyString(int n, int k) {
        // Total happy strings of length n is 3 * 2^(n - 1)
        int total = 3 * (1 << (n - 1));
        if (k > total) {
            return "";
        }

        // Convert to 0-indexed
        k--;

        StringBuilder sb = new StringBuilder();
        char[] chars = {'a', 'b', 'c'};

        // Determine the first character
        int blockSize = 1 << (n - 1);
        int firstIdx = k / blockSize;
        sb.append(chars[firstIdx]);
        k %= blockSize;

        // Determine each subsequent character
        for (int step = n - 2; step >= 0; step--) {
            blockSize = 1 << step;
            int idx = k / blockSize;
            char prev = sb.charAt(sb.length() - 1);

            // Select the idx-th character from available characters != prev
            int count = 0;
            for (char c : chars) {
                if (c != prev) {
                    if (count == idx) {
                        sb.append(c);
                        break;
                    }
                    count++;
                }
            }

            k %= blockSize;
        }

        return sb.toString();
    }
}

"""
Problem: LeetCode 1415 - The k-th Lexicographical String of All Happy Strings of Length n
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        # Total happy strings of length n is 3 * 2^(n - 1)
        total = 3 * (1 << (n - 1))
        if k > total:
            return ""

        # Convert to 0-indexed
        k -= 1
        res = []
        chars = ['a', 'b', 'c']

        # Determine the first character
        block_size = 1 << (n - 1)
        idx = k // block_size
        res.append(chars[idx])
        k %= block_size

        # Determine each subsequent character
        for step in range(n - 2, -1, -1):
            block_size = 1 << step
            idx = k // block_size
            prev = res[-1]
            available = [c for c in chars if c != prev]
            res.append(available[idx])
            k %= block_size

        return "".join(res)

/**
 * Problem: LeetCode 1415 - The k-th Lexicographical String of All Happy Strings of Length n
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    string getHappyString(int n, int k) {
        // Total happy strings of length n is 3 * 2^(n - 1)
        int total = 3 * (1 << (n - 1));
        if (k > total) {
            return "";
        }

        // Convert to 0-indexed
        k--;

        string result = "";
        char chars[] = {'a', 'b', 'c'};

        // Determine the first character
        int blockSize = 1 << (n - 1);
        int firstIdx = k / blockSize;
        result += chars[firstIdx];
        k %= blockSize;

        // Determine each subsequent character
        for (int step = n - 2; step >= 0; step--) {
            blockSize = 1 << step;
            int idx = k / blockSize;
            char prev = result.back();

            int count = 0;
            for (char c : chars) {
                if (c != prev) {
                    if (count == idx) {
                        result += c;
                        break;
                    }
                    count++;
                }
            }

            k %= blockSize;
        }

        return result;
    }
};

/**
 * Problem: LeetCode 1415 - The k-th Lexicographical String of All Happy Strings of Length n
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getHappyString = function(n, k) {
    // Total happy strings of length n is 3 * 2^(n - 1)
    const total = 3 * (1 << (n - 1));
    if (k > total) {
        return "";
    }

    // Convert to 0-indexed
    k--;

    const res = [];
    const chars = ['a', 'b', 'c'];

    // Determine the first character
    let blockSize = 1 << (n - 1);
    let idx = Math.floor(k / blockSize);
    res.push(chars[idx]);
    k %= blockSize;

    // Determine each subsequent character
    for (let step = n - 2; step >= 0; step--) {
        blockSize = 1 << step;
        idx = Math.floor(k / blockSize);
        const prev = res[res.length - 1];
        const available = chars.filter(c => c !== prev);
        res.push(available[idx]);
        k %= blockSize;
    }

    return res.join("");
};