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 9^th 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:

If the length of the current string is equal to $n$, add the current string to the answer array $\textit{ans}$ and return;
If the length of the answer array is greater than or equal to $k$, return directly;
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.

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.

class Solution {
    private List<String> ans = new ArrayList<>();

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

    private void dfs(String t, int n) {
        if (t.length() == n) {
            ans.add(t);
            return;
        }
        for (char c : "abc".toCharArray()) {
            if (t.length() > 0 && t.charAt(t.length() - 1) == c) {
                continue;
            }
            dfs(t + c, n);
        }
    }
}


// Solution 2
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();
    }
}

class Solution {
public:
    vector<string> ans;
    string getHappyString(int n, int k) {
        dfs("", n);
        return ans.size() < k ? "" : ans[k - 1];
    }

    void dfs(string t, int n) {
        if (t.size() == n) {
            ans.push_back(t);
            return;
        }
        for (int c = 'a'; c <= 'c'; ++c) {
            if (t.size() && t.back() == c) continue;
            t.push_back(c);
            dfs(t, n);
            t.pop_back();
        }
    }
};


// Solution 2
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;
    }
};

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        def dfs(t):
            if len(t) == n:
                ans.append(t)
                return
            for c in 'abc':
                if t and t[-1] == c:
                    continue
                dfs(t + c)

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


# Solution 2
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)

function getHappyString(n: number, k: number): string {
    const ans: string[] = [];

    const dfs = (s = '') => {
        if (s.length === n) {
            ans.push(s);
            return;
        }

        for (const ch of 'abc') {
            if (s.at(-1) === ch) continue;
            dfs(s + ch);
        }
    };

    dfs();

    return ans[k - 1] ?? '';
}


// Solution 2
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('');
}

function getHappyString(n, k) {
    const ans = [];

    const dfs = (s = '') => {
        if (s.length === n) {
            ans.push(s);
            return;
        }

        for (const ch of 'abc') {
            if (s.at(-1) === ch) continue;
            dfs(s + ch);
        }
    };

    dfs();

    return ans[k - 1] ?? '';
}


// Solution 2
/**
 * @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('');
};

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]
}


// Solution 2
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)
}

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
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();
    }
}

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()
        }
    }
}


// Solution 2
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()
    }
}

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

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

Description

Solutions

Solution 1: DFS

Solution 2: Mathematics

All Problems

All Solutions

Welcome to Subscribe On Youtube

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

Description

Solutions

Solution 1: DFS

Solution 2: Mathematics

All Problems

All Solutions