Jobs

Interviews

Discussions

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

Medium

Asked by:

More companies

31 views

Topics:

StringsRecursion

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

Try coding it in LeetCode

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

Medium

Asked by:

31 views

Topics:

StringsRecursion

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on `n` and `k`? Are they positive integers?
Is there a specific behavior expected if `k` is greater than the total number of happy strings of length `n`? Should I return an empty string or null, or is that considered an error?
By "lexicographical order", are we using the standard alphabetical order (a < b < c)?
Can `n` be zero? If so, what should the output be?
Should I handle invalid input cases, such as `n` being negative or `k` being zero, or can I assume the input is always valid?

Brute Force Solution

Approach

The brute force approach involves generating all possible strings that meet the 'happy string' criteria (no consecutive characters are the same) and are of the desired length. Then, we order these strings lexicographically (like in a dictionary) and select the k-th string. This is like trying every possible combination until we find the one we're looking for.

Here's how the algorithm would work step-by-step:

First, build every single possible string of the required length using only the letters 'a', 'b', and 'c'.
As you build each string, check if it's a 'happy string'. This means making sure no two letters next to each other are the same.
If a string has consecutive identical letters, throw it out and don't keep it.
Keep only the strings that are 'happy'.
Once you have all possible happy strings, sort them into dictionary order. Think of it like alphabetizing a list.
Finally, find the string that's at the position 'k' in the sorted list. That's your answer.

Code Implementation

def find_kth_lexicographical_happy_string(string_length, kth_string):
    happy_strings = []

    def generate_strings(current_string, length):
        if length == 0:
            # Base case: string of desired length reached
            is_happy = True
            for i in range(len(current_string) - 1):
                if current_string[i] == current_string[i + 1]:
                    is_happy = False
                    break

            if is_happy:
                happy_strings.append(current_string)

            return

        generate_strings(current_string + 'a', length - 1)
        generate_strings(current_string + 'b', length - 1)
        generate_strings(current_string + 'c', length - 1)

    generate_strings('', string_length)

    # Filter out non-happy strings
    filtered_happy_strings = []
    for potential_happy_string in happy_strings:
        is_happy = True
        for i in range(len(potential_happy_string) - 1):
            if potential_happy_string[i] == potential_happy_string[i + 1]:
                is_happy = False
                break

        if is_happy:
            filtered_happy_strings.append(potential_happy_string)

    # Sort the happy strings lexicographically.
    filtered_happy_strings.sort()

    # Return the kth happy string, if it exists.
    if kth_string <= len(filtered_happy_strings):
        return filtered_happy_strings[kth_string - 1]
    else:
        return ""

Big(O) Analysis

Time Complexity

O(3^n * n log(3^n)) – Generating all possible strings of length n using 'a', 'b', and 'c' takes O(3^n) time, as there are 3 choices for each of the n positions. Checking each generated string for the happy string property (no consecutive duplicates) takes O(n) time in the worst case. Therefore, generating and validating happy strings takes O(3^n * n) time. Finally, sorting the generated happy strings, which can have a maximum size of 3^n, takes O(3^n * log(3^n)) time. Combining these, the overall time complexity is dominated by O(3^n * n) + O(3^n * log(3^n)), which simplifies to O(3^n * n log(3^n)).

Space Complexity

O(3^n) – The algorithm constructs all possible happy strings of length n and stores them. In the worst case, most of the generated strings could be happy strings. The maximum number of happy strings would be close to 3^n, since each position can have 3 possible characters. Therefore, we store at most O(3^n) strings in a list or other data structure to sort, which is the dominant factor in the space complexity.

Optimal Solution

Approach

The goal is to find a specific 'happy' string based on its position in a sorted list of all such strings. Instead of creating all happy strings and then sorting, we directly construct the k-th string by making informed choices at each position, drastically reducing the computation.

Here's how the algorithm would work step-by-step:

Understand the constraints of a 'happy' string: no adjacent characters can be the same (like 'aba' is happy, but 'abb' is not).
Recognize that we can build the happy string character by character.
Figure out how many 'happy' strings start with 'a', 'b', and 'c' respectively for a given length.
Use the given position (k) to determine the first character of the string. For instance, if k is smaller than the number of strings starting with 'a', the first character is 'a'. Adjust k accordingly if necessary.
Once the first character is chosen, repeat the process for the second character, considering that it cannot be the same as the previous one. Use k and the number of valid options to decide the second character.
Continue this process until the entire string is built. At each step, we're essentially dividing the problem into smaller subproblems and efficiently selecting the next character based on its position in the lexicographical order.
If k exceeds the total count of happy strings for the given length, there is no string at that position; return an empty string.

Code Implementation

def get_happy_string(string_length, kth_string):
    number_of_happy_strings = 3 * (2**(string_length - 1))

    if kth_string > number_of_happy_strings:
        return ""

    result = ""
    available_characters = ['a', 'b', 'c']

    # Determine the first character based on k and total strings
    base_count = (2**(string_length - 1))
    if kth_string <= base_count:
        result += 'a'
    elif kth_string <= 2 * base_count:
        result += 'b'
        kth_string -= base_count
    else:
        result += 'c'
        kth_string -= 2 * base_count

    for _ in range(1, string_length):
        # Choose the next character, ensuring it's different
        next_available_chars = [char for char in available_characters if char != result[-1]]
        base_count //= 2

        # Reduce the problem size
        if kth_string <= base_count:
            result += next_available_chars[0]
        else:
            result += next_available_chars[1]
            kth_string -= base_count

    return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm builds the happy string character by character. For a string of length n, it iterates n times. In each iteration, it determines the next character based on the current position and the remaining k value, which takes constant time. Therefore, the time complexity is directly proportional to the length of the string, resulting in O(n).

Space Complexity

O(n) – The space complexity is dominated by the recursion depth, which corresponds to the length of the happy string, denoted by n. Each recursive call requires stack space to store the function's state, including local variables and return address. Therefore, the maximum space used by the call stack is proportional to the length of the string we're building, giving us a space complexity of O(n).

Edge Cases

Case	How to Handle
n is zero	Return an empty string, as there are no happy strings of length zero.
k is zero or negative	Return an empty string or throw an IllegalArgumentException as the kth element does not exist for non-positive k.
k is larger than the total number of happy strings of length n	Return an empty string or throw an IllegalArgumentException if k is too large; the maximum number of happy strings is 3 * 2^(n-1).
n is one	Handle this base case separately, returning 'a', 'b', or 'c' based on the value of k.
n is relatively large (e.g., 20)	Ensure that the algorithm used scales efficiently to avoid timeouts, favoring iterative approaches over naive recursion.
Integer overflow during calculation of total number of happy strings or index calculations	Use long data type to store and calculate the number of happy strings or intermediate indices to prevent overflow, or return an empty string if overflow is still possible.
n is negative	Throw an IllegalArgumentException if n is negative as string length cannot be negative.
Extreme values of n leading to memory exhaustion	Limit maximum n value to prevent excessive memory allocation and potential out of memory errors, or return an empty string.

n is zero

How to Handle:

Return an empty string, as there are no happy strings of length zero.

k is zero or negative

How to Handle:

Return an empty string or throw an IllegalArgumentException as the kth element does not exist for non-positive k.

k is larger than the total number of happy strings of length n

How to Handle:

Return an empty string or throw an IllegalArgumentException if k is too large; the maximum number of happy strings is 3 * 2^(n-1).

n is one

How to Handle:

Handle this base case separately, returning 'a', 'b', or 'c' based on the value of k.

n is relatively large (e.g., 20)

How to Handle:

Ensure that the algorithm used scales efficiently to avoid timeouts, favoring iterative approaches over naive recursion.

Integer overflow during calculation of total number of happy strings or index calculations

How to Handle:

Use long data type to store and calculate the number of happy strings or intermediate indices to prevent overflow, or return an empty string if overflow is still possible.

n is negative

How to Handle:

Throw an IllegalArgumentException if n is negative as string length cannot be negative.

Extreme values of n leading to memory exhaustion

How to Handle:

Limit maximum n value to prevent excessive memory allocation and potential out of memory errors, or return an empty string.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on `n` and `k`? Are they positive integers?
Is there a specific behavior expected if `k` is greater than the total number of happy strings of length `n`? Should I return an empty string or null, or is that considered an error?
By "lexicographical order", are we using the standard alphabetical order (a < b < c)?
Can `n` be zero? If so, what should the output be?
Should I handle invalid input cases, such as `n` being negative or `k` being zero, or can I assume the input is always valid?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, build every single possible string of the required length using only the letters 'a', 'b', and 'c'.
As you build each string, check if it's a 'happy string'. This means making sure no two letters next to each other are the same.
If a string has consecutive identical letters, throw it out and don't keep it.
Keep only the strings that are 'happy'.
Once you have all possible happy strings, sort them into dictionary order. Think of it like alphabetizing a list.
Finally, find the string that's at the position 'k' in the sorted list. That's your answer.

Code Implementation

def find_kth_lexicographical_happy_string(string_length, kth_string):
    happy_strings = []

    def generate_strings(current_string, length):
        if length == 0:
            # Base case: string of desired length reached
            is_happy = True
            for i in range(len(current_string) - 1):
                if current_string[i] == current_string[i + 1]:
                    is_happy = False
                    break

            if is_happy:
                happy_strings.append(current_string)

            return

        generate_strings(current_string + 'a', length - 1)
        generate_strings(current_string + 'b', length - 1)
        generate_strings(current_string + 'c', length - 1)

    generate_strings('', string_length)

    # Filter out non-happy strings
    filtered_happy_strings = []
    for potential_happy_string in happy_strings:
        is_happy = True
        for i in range(len(potential_happy_string) - 1):
            if potential_happy_string[i] == potential_happy_string[i + 1]:
                is_happy = False
                break

        if is_happy:
            filtered_happy_strings.append(potential_happy_string)

    # Sort the happy strings lexicographically.
    filtered_happy_strings.sort()

    # Return the kth happy string, if it exists.
    if kth_string <= len(filtered_happy_strings):
        return filtered_happy_strings[kth_string - 1]
    else:
        return ""

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Understand the constraints of a 'happy' string: no adjacent characters can be the same (like 'aba' is happy, but 'abb' is not).
Recognize that we can build the happy string character by character.
Figure out how many 'happy' strings start with 'a', 'b', and 'c' respectively for a given length.
Use the given position (k) to determine the first character of the string. For instance, if k is smaller than the number of strings starting with 'a', the first character is 'a'. Adjust k accordingly if necessary.
Once the first character is chosen, repeat the process for the second character, considering that it cannot be the same as the previous one. Use k and the number of valid options to decide the second character.
Continue this process until the entire string is built. At each step, we're essentially dividing the problem into smaller subproblems and efficiently selecting the next character based on its position in the lexicographical order.
If k exceeds the total count of happy strings for the given length, there is no string at that position; return an empty string.

Code Implementation

def get_happy_string(string_length, kth_string):
    number_of_happy_strings = 3 * (2**(string_length - 1))

    if kth_string > number_of_happy_strings:
        return ""

    result = ""
    available_characters = ['a', 'b', 'c']

    # Determine the first character based on k and total strings
    base_count = (2**(string_length - 1))
    if kth_string <= base_count:
        result += 'a'
    elif kth_string <= 2 * base_count:
        result += 'b'
        kth_string -= base_count
    else:
        result += 'c'
        kth_string -= 2 * base_count

    for _ in range(1, string_length):
        # Choose the next character, ensuring it's different
        next_available_chars = [char for char in available_characters if char != result[-1]]
        base_count //= 2

        # Reduce the problem size
        if kth_string <= base_count:
            result += next_available_chars[0]
        else:
            result += next_available_chars[1]
            kth_string -= base_count

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n is zero	Return an empty string, as there are no happy strings of length zero.
k is zero or negative	Return an empty string or throw an IllegalArgumentException as the kth element does not exist for non-positive k.
k is larger than the total number of happy strings of length n	Return an empty string or throw an IllegalArgumentException if k is too large; the maximum number of happy strings is 3 * 2^(n-1).
n is one	Handle this base case separately, returning 'a', 'b', or 'c' based on the value of k.
n is relatively large (e.g., 20)	Ensure that the algorithm used scales efficiently to avoid timeouts, favoring iterative approaches over naive recursion.
Integer overflow during calculation of total number of happy strings or index calculations	Use long data type to store and calculate the number of happy strings or intermediate indices to prevent overflow, or return an empty string if overflow is still possible.
n is negative	Throw an IllegalArgumentException if n is negative as string length cannot be negative.
Extreme values of n leading to memory exhaustion	Limit maximum n value to prevent excessive memory allocation and potential out of memory errors, or return an empty string.

n is zero

How to Handle:

Return an empty string, as there are no happy strings of length zero.

k is zero or negative

How to Handle:

Return an empty string or throw an IllegalArgumentException as the kth element does not exist for non-positive k.

k is larger than the total number of happy strings of length n

How to Handle:

Return an empty string or throw an IllegalArgumentException if k is too large; the maximum number of happy strings is 3 * 2^(n-1).

n is one

How to Handle:

Handle this base case separately, returning 'a', 'b', or 'c' based on the value of k.

n is relatively large (e.g., 20)

How to Handle:

Ensure that the algorithm used scales efficiently to avoid timeouts, favoring iterative approaches over naive recursion.

Integer overflow during calculation of total number of happy strings or index calculations

How to Handle:

Use long data type to store and calculate the number of happy strings or intermediate indices to prevent overflow, or return an empty string if overflow is still possible.

n is negative

How to Handle:

Throw an IllegalArgumentException if n is negative as string length cannot be negative.

Extreme values of n leading to memory exhaustion

How to Handle:

Limit maximum n value to prevent excessive memory allocation and potential out of memory errors, or return an empty string.