Problem Explanation

A happy string is defined as a string that contains only letters 'a', 'b' and 'c' such that no two consecutive letters are the same. We are given two integers n and k. We are required to create a list of all possible happy strings of length 'n' sorted in lexicographically order and return the k-th string from the list. If there are less than 'k' happy strings of length 'n', we return an empty string.

For instance, let's consider an example where n = 3 and k = 9. For happy strings of length 3, there are 12 possible combinations - ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"]. The k-th (9th) string in the list is "cab".

Approach

To solve this problem an algorithm has been used which performs a breadth-first search (BFS). Since the problem requires to generate the lexicographical order, and a BFS can naturally generate the lexicographically minimal string first, this is the ideal algorithm to use for this problem.

The algorithm uses a queue to store the happy strings generated so far. It starts with the queue containing the single letter happy strings "a", "b", and "c". The algorithm continues to generate longer happy strings by iteratively appending the next possible letters (different from the current last letter) to the string at the front of the queue and removing the string from the front of the queue, until it generates happy strings of the required length.

The algorithm then checks if the number of the happy strings generated is less than 'k'. If it is, it returns an empty string as there are less than 'k' happy strings of the required length.

Otherwise, it discards the first 'k - 1' happy strings and returns the k-th happy string in the queue.

Python Solution

1
2python
3import collections
4
5class Solution:
6    def getHappyString(self, n: int, k: int) -> str:
7        happy = ['a', 'b', 'c']
8        queue = collections.deque(happy)
9
10        while len(queue[0]) != n:
11            u = queue.popleft()
12            for char in [c for c in happy if c != u[-1]]:
13                queue.append(u + char)
14
15        return queue[k-1] if len(queue) >= k else ""

Java Solution

1
2java
3class Solution {
4    public String getHappyString(int n, int k) {
5        char[] chars = {'a', 'b', 'c'};
6        Queue<String> queue = new LinkedList<>(Arrays.asList("a", "b", "c"));
7        
8        while(queue.peek().length() != n) {
9            String s = queue.poll();
10            for(char c: chars) {
11                if(s.charAt(s.length() - 1) != c) {
12                    queue.add(s + c);
13                }
14            }
15        }
16        
17        while(--k > 0 && !queue.isEmpty()) {
18            queue.poll();
19        }
20        
21        return k == 0 ? queue.poll() : "";
22    }
23}

JavaScript Solution

1
2javascript
3class Solution {
4    getHappyString(n, k) {
5        let queue = ['a', 'b', 'c'];
6        
7        while(queue[0].length != n) {
8            let s = queue.shift();
9            for(let c of ['a', 'b', 'c']) {
10                if(s.slice(-1) != c) {
11                    queue.push(s + c);
12                }
13            }
14        }
15        
16        while(--k > 0 && queue.length){
17            queue.shift();
18        }
19        
20        return k == 0 ? queue.shift() : "";
21    }
22}

C++ Solution

1
2c++
3class Solution {
4public:
5    string getHappyString(int n, int k) {
6        char nextLetters[3][2] = {{'b', 'c'}, {'a', 'c'}, {'a', 'b'}};
7        queue<string> q{{"a", "b", "c"}};
8
9        while (q.front().length() != n) {
10            string u = q.front(); q.pop();
11            for (char nextLetter : nextLetters[u.back() - 'a'])
12                q.push(u + nextLetter);
13        }
14
15        if (q.size() < k)
16            return "";
17
18        while (--k > 0 && !q.empty())
19            q.pop();
20        
21        return q.front();
22    }
23};

C# Solution

1
2csharp
3public class Solution {
4    public string GetHappyString(int n, int k) {
5        var nextLetters = new Dictionary<char, List<char>> {
6            {'a', new List<char>{'b', 'c'}},
7            {'b', new List<char>{'a', 'c'}},
8            {'c', new List<char>{'a', 'b'}}
9        };
10        var q = new Queue<string>(new []{"a", "b", "c"});
11
12        while (q.Peek().Length != n) {
13            var u = q.Dequeue();
14            foreach (var nextLetter in nextLetters[u.Last()])
15                q.Enqueue(u + nextLetter);
16        }
17
18        while (--k > 0 && q.Count > 0)
19            q.Dequeue();
20        
21        return k == 0 ? q.Dequeue() : string.Empty;
22    }
23}

In all the solutions, the function getHappyString takes two arguments n and k and returns the k-th lexicographical happy string of length n. If such a happy string does not exist, it returns an empty string. The time complexity of all the solutions is O(3^n), which is because in the worst case, the algorithm generates all possible happy strings of length n. The space complexity is also O(3^n), because in the worst case, the algorithm needs to store all possible happy strings of length n in the queue.All of these solutions follow the same overall approach, but there are a few things that differ between the Python, Java, JavaScript, C++ and C# solutions.

The Python solution uses the inbuilt deque from the collections module, ensuring fast and efficient operations. It's also notable that it uses list comprehension to create new happy strings.

The Java solution, JavaScript, C++ and C# solutions are analogous to the Python solution but with specific features of each language.

The C# solution uses a Dictionary to ensure fast look-up of nextLetters. It uses LINQ's Last method to access the last character of a string. Unlike the other solutions, it dequeues the k-1 strings and checks if the queue is not empty in the same while loop.

All of these solutions provide efficient ways to solve the problem in their respective programming languages. It's worth noting that the kind of approach used here, often called a breadth-first search, is a common technique in computer science for traversing or searching tree or graph data structures. It's often used when we want to visit all the nodes at the present level before going to a deeper level.