Depth First Search Algoritm to Compute The k-th Lexicographical String of All Happy Strings of Length n

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

Example 1:
Input: n = 1, k = 3
Output: “c”
Explanation: The list [“a”, “b”, “c”] contains all happy strings of length 1. The third string is “c”.

Example 2:
Input: n = 1, k = 4
Output: “”
Explanation: There are only 3 happy strings of length 1.

Example 3:
Input: n = 3, k = 9
Output: “cab”
Explanation: There are 12 different happy string of length 3 [“aba”, “abc”, “aca”, “acb”, “bab”, “bac”, “bca”, “bcb”, “cab”, “cac”, “cba”, “cbc”]. You will find the 9th string = “cab”

Example 4:
Input: n = 2, k = 7
Output: “”

Example 5:
Input: n = 10, k = 100
Output: “abacbabacb”

Constraints:
1 <= n <= 10
1 <= k <= 100

Hints:
Generate recursively all the happy strings of length n.
Sort them in lexicographical order and return the kth string if it exists.

Compute The k-th Lexicographical String of All Happy Strings of Length n using Depth First Search Algorithm

The input constraints says the N is maximum 10, and thus, we can just generate all the happy sequences using DFS algorithm. The following C++ uses Recursion to generate all the valid candidates and push them into a vector.

When we recursively call the DFS function, we push only to the next character when it is not the same as the previous. Then, when we have the N-size string, we know it is a happy string.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    string getHappyString(int n, int k) {
        vector<string> result;
        dfs(result, "", n);
        if (k <= result.size()) return result[k - 1];
        return "";
    }
private:
    void dfs(vector<string> &result, string cur, int n) {
        if (cur.size() == n) {
            result.push_back(cur);
            return;
        }
        char last = (cur == "") ? ' ' : cur.back();
        for (char x = 'a'; x <= 'c'; x ++) {
            if (x != last) {
                dfs(result, cur + x, n);
            }
        }
    }
};

class Solution {
public:
    string getHappyString(int n, int k) {
        vector<string> result;
        dfs(result, "", n);
        if (k <= result.size()) return result[k - 1];
        return "";
    }
private:
    void dfs(vector<string> &result, string cur, int n) {
        if (cur.size() == n) {
            result.push_back(cur);
            return;
        }
        char last = (cur == "") ? ' ' : cur.back();
        for (char x = 'a'; x <= 'c'; x ++) {
            if (x != last) {
                dfs(result, cur + x, n);
            }
        }
    }
};

Given size N, there are 3*2^(n-1) happy strings – which is the complexity of the recursive algorithm. The space requirement is also the same as we need to allocate space for storing all the happy strings plus the implicit calling stacks due to recursion.

–EOF (The Ultimate Computing & Technology Blog) —