Chuỗi hạnh phúc thứ k theo thứ tự từ điển (The k-th Lexicographical String of All Happy Strings of Length n) trong C++

Chuỗi "hạnh phúc" (happy string): chỉ chứa 'a','b','c' và không có 2 ký tự liền kề giống nhau. Cho n, k. Liệt kê tất cả happy strings độ dài n theo thứ tự từ điển, trả về chuỗi thứ k (1-indexed) hoặc rỗng nếu không đủ.

Ví dụ

Đầu vào: n = 3, k = 9
Đầu ra: "cab" (12 chuỗi: aba,abc,aca,acb,bab,bac,bca,bcb,cab,cac,cba,cbc).

Thuật toán DFS sinh theo thứ tự từ điển

1. DFS xây dựng chuỗi: bắt đầu từ 'a','b','c'.
2. Tại mỗi bước, thêm ký tự khác ký tự cuối.
3. Khi độ dài = n: lưu vào kết quả.
4. Vì duyệt 'a'→'b'→'c', kết quả tự động theo thứ tự từ điển.
5. Nếu k > kết quả.size() trả về rỗng, ngược lại trả về res[k-1].

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
    vector res;
    char ch[3] = {'a','b','c'};
    int targetLen;
    void dfs(string s, int len) {
        if (len == targetLen) { res.push_back(s); return; }
        for (int i = 0; i < 3; ++i)
            if (s.back() != ch[i])
                dfs(s + ch[i], len + 1);
    }
public:
    string getHappyString(int n, int k) {
        targetLen = n;
        if (n == 0) return "";
        dfs("a", 1); dfs("b", 1); dfs("c", 1);
        return (k > res.size()) ? "" : res[k-1];
    }
};

Độ phức tạp

• Thời gian: O(3 * 2^(n-1)) - số lượng happy strings.
• Không gian: O(3 * 2^(n-1) * n) lưu kết quả (có thể tối ưu dừng sớm khi đủ k).

Kết quả kiểm thử

Đầu vào: 3,9
Đầu ra: cab