Skip to content

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

Description

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"

Β 

Constraints:

  • 1 <= n <= 10
  • 1 <= k <= 100

Solutions

Solution 1: DFS

We use a string \(\textit{s}\) to record the current string, initially an empty string. Then, we design a function \(\text{dfs}\) to generate all happy strings of length \(n\).

The implementation of the function \(\text{dfs}\) is as follows:

  1. If the length of the current string is equal to \(n\), add the current string to the answer array \(\textit{ans}\) and return;
  2. If the length of the answer array is greater than or equal to \(k\), return directly;
  3. Otherwise, we iterate over the character set \(\{a, b, c\}\). For each character \(c\), if the current string is empty or the last character of the current string is not equal to \(c\), add the character \(c\) to the current string, then recursively call \(\text{dfs}\). After the recursion ends, remove the last character of the current string.

Finally, we check if the length of the answer array is less than \(k\). If it is, return an empty string; otherwise, return the \(k\)-th element of the answer array.

The time complexity is \(O(n \times 2^n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the string.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        def dfs():
            if len(s) == n:
                ans.append("".join(s))
                return
            if len(ans) >= k:
                return
            for c in "abc":
                if not s or s[-1] != c:
                    s.append(c)
                    dfs()
                    s.pop()

        ans = []
        s = []
        dfs()
        return "" if len(ans) < k else ans[k - 1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    private List<String> ans = new ArrayList<>();
    private StringBuilder s = new StringBuilder();
    private int n, k;

    public String getHappyString(int n, int k) {
        this.n = n;
        this.k = k;
        dfs();
        return ans.size() < k ? "" : ans.get(k - 1);
    }

    private void dfs() {
        if (s.length() == n) {
            ans.add(s.toString());
            return;
        }
        if (ans.size() >= k) {
            return;
        }
        for (char c : "abc".toCharArray()) {
            if (s.isEmpty() || s.charAt(s.length() - 1) != c) {
                s.append(c);
                dfs();
                s.deleteCharAt(s.length() - 1);
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    string getHappyString(int n, int k) {
        vector<string> ans;
        string s = "";
        auto dfs = [&](this auto&& dfs) -> void {
            if (s.size() == n) {
                ans.emplace_back(s);
                return;
            }
            if (ans.size() >= k) {
                return;
            }
            for (char c = 'a'; c <= 'c'; ++c) {
                if (s.empty() || s.back() != c) {
                    s.push_back(c);
                    dfs();
                    s.pop_back();
                }
            }
        };
        dfs();
        return ans.size() < k ? "" : ans[k - 1];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func getHappyString(n int, k int) string {
    ans := []string{}
    var s []byte

    var dfs func()
    dfs = func() {
        if len(s) == n {
            ans = append(ans, string(s))
            return
        }
        if len(ans) >= k {
            return
        }
        for c := byte('a'); c <= 'c'; c++ {
            if len(s) == 0 || s[len(s)-1] != c {
                s = append(s, c)
                dfs()
                s = s[:len(s)-1]
            }
        }
    }

    dfs()
    if len(ans) < k {
        return ""
    }
    return ans[k-1]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
function getHappyString(n: number, k: number): string {
    const ans: string[] = [];
    const s: string[] = [];
    const dfs = () => {
        if (s.length === n) {
            ans.push(s.join(''));
            return;
        }
        if (ans.length >= k) {
            return;
        }
        for (const c of 'abc') {
            if (!s.length || s.at(-1)! !== c) {
                s.push(c);
                dfs();
                s.pop();
            }
        }
    };
    dfs();
    return ans[k - 1] ?? '';
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
impl Solution {
    pub fn get_happy_string(n: i32, k: i32) -> String {
        let mut ans = Vec::new();
        let mut s = String::new();
        let mut k = k;

        fn dfs(n: i32, s: &mut String, ans: &mut Vec<String>, k: &mut i32) {
            if s.len() == n as usize {
                ans.push(s.clone());
                return;
            }
            if ans.len() >= *k as usize {
                return;
            }
            for c in "abc".chars() {
                if s.is_empty() || s.chars().last() != Some(c) {
                    s.push(c);
                    dfs(n, s, ans, k);
                    s.pop();
                }
            }
        }

        dfs(n, &mut s, &mut ans, &mut k);
        if ans.len() < k as usize {
            "".to_string()
        } else {
            ans[(k - 1) as usize].clone()
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getHappyString = function (n, k) {
    const ans = [];
    const s = [];
    const dfs = () => {
        if (s.length === n) {
            ans.push(s.join(''));
            return;
        }
        if (ans.length >= k) {
            return;
        }
        for (const c of 'abc') {
            if (!s.length || s.at(-1) !== c) {
                s.push(c);
                dfs();
                s.pop();
            }
        }
    };
    dfs();
    return ans[k - 1] ?? '';
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public string GetHappyString(int n, int k) {
        List<string> ans = new List<string>();
        StringBuilder s = new StringBuilder();

        void Dfs() {
            if (s.Length == n) {
                ans.Add(s.ToString());
                return;
            }
            if (ans.Count >= k) {
                return;
            }
            foreach (char c in "abc") {
                if (s.Length == 0 || s[s.Length - 1] != c) {
                    s.Append(c);
                    Dfs();
                    s.Length--;
                }
            }
        }

        Dfs();
        return ans.Count < k ? "" : ans[k - 1];
    }
}

Solution 2: Mathematics

We can directly calculate what the \(k\)-th happy string is, without generating all happy strings.

Starting from the first happy string of length \(n\), we can determine what each character position should be.

For a happy string of length \(n\), the first character has \(3\) choices, the second character has \(2\) choices (cannot be the same as the first), the third character also has \(2\) choices (cannot be the same as the second), and so on, until the \(n\)-th character also has \(2\) choices (cannot be the same as the \((n-1)\)-th). Therefore, the total number of happy strings of length \(n\) is \(3 \times 2^{n-1}\).

If \(k\) is greater than the total number of happy strings of length \(n\), we return an empty string directly.

Otherwise, we start from the first character and determine each character's position one by one. For the \(i\)-th character, we enumerate the character set \(\{a, b, c\}\). If the last character of the current string is not equal to \(c\), we calculate the number of remaining happy strings. If \(k\) is less than or equal to that count, we append character \(c\) to the current string and move on to the next position; otherwise, we subtract that count from \(k\) and continue enumerating the next character.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the length of the string.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        if k > 3 * (1 << (n - 1)):
            return ""
        cs = "abc"
        ans = []
        for i in range(n):
            remain = 1 << (n - i - 1)
            for c in cs:
                if ans and ans[-1] == c:
                    continue
                if k <= remain:
                    ans.append(c)
                    break
                k -= remain
        return "".join(ans)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public String getHappyString(int n, int k) {
        if (k > 3 * (1 << (n - 1))) {
            return "";
        }
        String cs = "abc";
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < n; i++) {
            int remain = 1 << (n - i - 1);
            for (char c : cs.toCharArray()) {
                if (ans.length() > 0 && ans.charAt(ans.length() - 1) == c) {
                    continue;
                }
                if (k <= remain) {
                    ans.append(c);
                    break;
                }
                k -= remain;
            }
        }
        return ans.toString();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string getHappyString(int n, int k) {
        if (k > 3 * (1 << (n - 1))) {
            return "";
        }
        string cs = "abc";
        string ans;
        for (int i = 0; i < n; ++i) {
            int remain = 1 << (n - i - 1);
            for (char c : cs) {
                if (!ans.empty() && ans.back() == c) {
                    continue;
                }
                if (k <= remain) {
                    ans.push_back(c);
                    break;
                }
                k -= remain;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func getHappyString(n int, k int) string {
    if k > 3*(1<<(n-1)) {
        return ""
    }
    cs := "abc"
    ans := make([]byte, 0, n)
    for i := 0; i < n; i++ {
        remain := 1 << (n - i - 1)
        for j := 0; j < len(cs); j++ {
            c := cs[j]
            if len(ans) > 0 && ans[len(ans)-1] == c {
                continue
            }
            if k <= remain {
                ans = append(ans, c)
                break
            }
            k -= remain
        }
    }
    return string(ans)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
function getHappyString(n: number, k: number): string {
    if (k > 3 * (1 << (n - 1))) {
        return '';
    }
    const cs = 'abc';
    const ans: string[] = [];
    for (let i = 0; i < n; i++) {
        const remain = 1 << (n - i - 1);
        for (const c of cs) {
            if (ans.at(-1) === c) {
                continue;
            }
            if (k <= remain) {
                ans.push(c);
                break;
            }
            k -= remain;
        }
    }
    return ans.join('');
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
impl Solution {
    pub fn get_happy_string(n: i32, mut k: i32) -> String {
        if k > 3 * (1 << (n - 1)) {
            return String::new();
        }
        let cs = ['a', 'b', 'c'];
        let mut ans: Vec<char> = Vec::with_capacity(n as usize);
        for i in 0..n {
            let remain = 1 << (n - i - 1);
            for &c in &cs {
                if !ans.is_empty() && *ans.last().unwrap() == c {
                    continue;
                }
                if k <= remain {
                    ans.push(c);
                    break;
                }
                k -= remain;
            }
        }
        ans.into_iter().collect()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getHappyString = function (n, k) {
    if (k > 3 * (1 << (n - 1))) {
        return '';
    }
    const cs = 'abc';
    const ans = [];
    for (let i = 0; i < n; i++) {
        const remain = 1 << (n - i - 1);
        for (let j = 0; j < cs.length; j++) {
            const c = cs[j];
            if (ans.at(-1) === c) {
                continue;
            }
            if (k <= remain) {
                ans.push(c);
                break;
            }
            k -= remain;
        }
    }
    return ans.join('');
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public string GetHappyString(int n, int k) {
        if (k > 3 * (1 << (n - 1))) {
            return "";
        }
        string cs = "abc";
        var ans = new System.Text.StringBuilder();
        for (int i = 0; i < n; i++) {
            int remain = 1 << (n - i - 1);
            foreach (char c in cs) {
                if (ans.Length > 0 && ans[ans.Length - 1] == c) {
                    continue;
                }
                if (k <= remain) {
                    ans.Append(c);
                    break;
                }
                k -= remain;
            }
        }
        return ans.ToString();
    }
}

Comments