Jobs

Interviews

Discussions

Longest Happy String

Medium

Wayfair

2 views

Topics:

Greedy AlgorithmsStrings

A string s is called happy if it satisfies the following conditions:

s only contains the letters 'a', 'b', and 'c'.
s does not contain any of "aaa", "bbb", or "ccc" as a substring.
s contains at most a occurrences of the letter 'a'.
s contains at most b occurrences of the letter 'b'.
s contains at most c occurrences of the letter 'c'.

Given three integers a, b, and c, return the longest possible happy string. If there are multiple longest happy strings, return any of them. If there is no such string, return the empty string "".

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.

Example 2:

Input: a = 7, b = 1, c = 0
Output: "aabaa"
Explanation: It is the only correct answer in this case.

Constraints:

0 <= a, b, c <= 100
a + b + c > 0

Try coding it in LeetCode

Longest Happy String

Medium

Wayfair

2 views

Topics:

Greedy AlgorithmsStrings

A string s is called happy if it satisfies the following conditions:

s only contains the letters 'a', 'b', and 'c'.
s does not contain any of "aaa", "bbb", or "ccc" as a substring.
s contains at most a occurrences of the letter 'a'.
s contains at most b occurrences of the letter 'b'.
s contains at most c occurrences of the letter 'c'.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.

Example 2:

Input: a = 7, b = 1, c = 0
Output: "aabaa"
Explanation: It is the only correct answer in this case.

Constraints:

0 <= a, b, c <= 100
a + b + c > 0

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 possible ranges for the input integers a, b, and c?
If it's impossible to construct a 'happy string', what should I return (e.g., an empty string, null)?
If multiple valid 'happy strings' exist, is any one acceptable, or is there a specific criterion for choosing one?
Are a, b, and c guaranteed to be non-negative integers?
By 'happy string', do you mean that there can be no consecutive substrings of 'aaa', 'bbb', or 'ccc' longer than or equal to 3 characters?

Brute Force Solution

Approach

The brute force approach to building the longest happy string is like trying every single possible combination of 'a's, 'b's, and 'c's until we find one that satisfies the 'happy' condition (no three consecutive identical characters). We generate every possible string and then check if it's valid.

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

Start with an empty string.
Try adding 'a' to the string. Then try adding 'b', and then 'c'.
For each of those resulting strings, again try adding 'a', 'b', and 'c' to each of them.
Keep doing this, building up longer and longer strings, making sure that we never use more 'a's, 'b's, or 'c's than we were given as input.
Each time we create a new string, check to see if it violates the 'happy' condition (three of the same letter in a row). If it does, throw it away.
Once we've tried every possible combination and reached the maximum number of 'a's, 'b's, and 'c's that we were given, look at all the valid (happy) strings we made.
Pick the longest valid string from all the ones we created. That's the longest happy string.

Code Implementation

def longest_happy_string_brute_force(a_count, b_count, c_count): 
    longest_happy_string = ""

    def is_valid(current_string):
        if len(current_string) < 3:
            return True
        return not (current_string[-1] == current_string[-2] == current_string[-3])

    def generate(current_string, remaining_a_count, remaining_b_count, remaining_c_count):
        nonlocal longest_happy_string

        if remaining_a_count < 0 or remaining_b_count < 0 or remaining_c_count < 0:
            return

        if not is_valid(current_string):
            return

        if len(current_string) > len(longest_happy_string):
            longest_happy_string = current_string

        # Attempt to add 'a' to the string
        generate(current_string + 'a', remaining_a_count - 1, remaining_b_count, remaining_c_count)

        # Attempt to add 'b' to the string
        generate(current_string + 'b', remaining_a_count, remaining_b_count - 1, remaining_c_count)

        # Attempt to add 'c' to the string
        generate(current_string + 'c', remaining_a_count, remaining_b_count, remaining_c_count - 1)

    generate("", a_count, b_count, c_count)

    return longest_happy_string

Big(O) Analysis

Time Complexity

O(3^(a+b+c)) – The brute force approach explores all possible combinations of 'a', 'b', and 'c' up to the given counts. In the worst-case scenario, where a, b, and c are relatively equal, the number of possible strings we generate grows exponentially. At each step, we have 3 choices ('a', 'b', or 'c'), and we can take up to 'a+b+c' steps. Therefore, the total number of strings explored is proportional to 3^(a+b+c), making the time complexity O(3^(a+b+c)).

Space Complexity

O(3^N) – The brute force approach explores all possible combinations of 'a', 'b', and 'c' up to a maximum length dictated by the input counts for each character. This generates a tree-like structure where each node represents a string and each branch represents adding a character. Since we try three characters ('a', 'b', 'c') at each step, the number of possible strings grows exponentially, leading to potentially 3^N strings being stored at some point where N is the sum of the input counts of a, b, and c. Although invalid strings are discarded, the algorithm still explores and temporarily stores a large number of strings in memory, specifically during the string generation phase before validity checks. Therefore, the space complexity is O(3^N).

Optimal Solution

Approach

The goal is to create the longest possible string with the constraint that we can't have three consecutive identical characters. We achieve this by greedily picking the most frequent character, but being careful not to overuse it and violate the three-in-a-row rule.

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

Keep track of how many of each character (A, B, and C) are remaining.
Always try to use the character with the largest remaining count first.
If adding that character would create three in a row, choose the next most frequent character instead.
If we can't add any character without violating the three-in-a-row rule, then we're done; we've made the longest possible string.
Repeat these steps until we run out of characters or hit a dead end.
By always choosing the most frequent character that doesn't violate the rule, we ensure we build the string as efficiently as possible.

Code Implementation

def longest_happy_string(a_count, b_count, c_count):
    result_string = ""
    remaining_counts = [['a', a_count], ['b', b_count], ['c', c_count]]

    while True:
        remaining_counts.sort(key=lambda item: item[1], reverse=True)
        found = False

        for i in range(3):
            if remaining_counts[i][1] <= 0:
                continue

            # Prevent three consecutive chars
            if len(result_string) >= 2 and result_string[-1] == remaining_counts[i][0] and result_string[-2] == remaining_counts[i][0]:
                continue

            result_string += remaining_counts[i][0]
            remaining_counts[i][1] -= 1
            found = True
            break

        # If we can't add any character, we're done.
        if not found:
            break

    return result_string

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates, greedily appending characters to the result string. In each iteration, it prioritizes the most frequent character, potentially examining all three character counts (a, b, c) to determine which one is the best to use without violating the 'three in a row' constraint. Critically, each character is appended to the string at most its initial count times. Therefore, the number of iterations and thus the runtime is bounded by the sum of the initial counts of a, b, and c, which relates to the length of the final string, n. Consequently, the time complexity is O(n).

Space Complexity

O(1) – The algorithm keeps track of the remaining counts of the three characters (A, B, and C). These counts are stored in variables, which consume a constant amount of space regardless of the input values a, b, and c. No dynamic data structures like arrays, lists, or hash maps are created. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
a, b, and c are all zero	Return an empty string as no 'happy' string can be constructed.
One of a, b, or c is significantly larger than the sum of the other two (e.g., a = 100, b = 1, c = 1)	Prioritize the largest count, but ensure no three consecutive characters are the same to avoid violating 'happy' constraints.
a, b, and c are all equal	Construct the string by alternating the characters as much as possible to ensure all characters are included without exceeding length 2*count.
The sum of a, b, and c is very large potentially causing memory issues	The algorithm's space complexity scales linearly with the input counts so consider limiting the maximum allowed sum of a, b, and c.
Two of a, b, and c are zero	Return a string containing only the character associated with the non-zero count, limited to a length of the count itself.
All three counts are non-zero but very small (e.g., a=1, b=1, c=1)	Ensure correct handling of all permutations as all characters must be present in the output.
No valid solution exists because the counts are so skewed.	The algorithm handles this gracefully by prioritizing the highest count, and when no character can be appended without violating 'happy' constraints, it terminates and returns the best result generated.
Integer overflow when computing the length of the string	Ensure that you use a data type capable of holding values equal to the maximum possible sum of a, b, and c (e.g., int64_t in C++, long in Java, etc.)

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 possible ranges for the input integers a, b, and c?
If it's impossible to construct a 'happy string', what should I return (e.g., an empty string, null)?
If multiple valid 'happy strings' exist, is any one acceptable, or is there a specific criterion for choosing one?
Are a, b, and c guaranteed to be non-negative integers?
By 'happy string', do you mean that there can be no consecutive substrings of 'aaa', 'bbb', or 'ccc' longer than or equal to 3 characters?

Brute Force Solution

Approach

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

Start with an empty string.
Try adding 'a' to the string. Then try adding 'b', and then 'c'.
For each of those resulting strings, again try adding 'a', 'b', and 'c' to each of them.
Keep doing this, building up longer and longer strings, making sure that we never use more 'a's, 'b's, or 'c's than we were given as input.
Each time we create a new string, check to see if it violates the 'happy' condition (three of the same letter in a row). If it does, throw it away.
Once we've tried every possible combination and reached the maximum number of 'a's, 'b's, and 'c's that we were given, look at all the valid (happy) strings we made.
Pick the longest valid string from all the ones we created. That's the longest happy string.

Code Implementation

def longest_happy_string_brute_force(a_count, b_count, c_count): 
    longest_happy_string = ""

    def is_valid(current_string):
        if len(current_string) < 3:
            return True
        return not (current_string[-1] == current_string[-2] == current_string[-3])

    def generate(current_string, remaining_a_count, remaining_b_count, remaining_c_count):
        nonlocal longest_happy_string

        if remaining_a_count < 0 or remaining_b_count < 0 or remaining_c_count < 0:
            return

        if not is_valid(current_string):
            return

        if len(current_string) > len(longest_happy_string):
            longest_happy_string = current_string

        # Attempt to add 'a' to the string
        generate(current_string + 'a', remaining_a_count - 1, remaining_b_count, remaining_c_count)

        # Attempt to add 'b' to the string
        generate(current_string + 'b', remaining_a_count, remaining_b_count - 1, remaining_c_count)

        # Attempt to add 'c' to the string
        generate(current_string + 'c', remaining_a_count, remaining_b_count, remaining_c_count - 1)

    generate("", a_count, b_count, c_count)

    return longest_happy_string

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Keep track of how many of each character (A, B, and C) are remaining.
Always try to use the character with the largest remaining count first.
If adding that character would create three in a row, choose the next most frequent character instead.
If we can't add any character without violating the three-in-a-row rule, then we're done; we've made the longest possible string.
Repeat these steps until we run out of characters or hit a dead end.
By always choosing the most frequent character that doesn't violate the rule, we ensure we build the string as efficiently as possible.

Code Implementation

def longest_happy_string(a_count, b_count, c_count):
    result_string = ""
    remaining_counts = [['a', a_count], ['b', b_count], ['c', c_count]]

    while True:
        remaining_counts.sort(key=lambda item: item[1], reverse=True)
        found = False

        for i in range(3):
            if remaining_counts[i][1] <= 0:
                continue

            # Prevent three consecutive chars
            if len(result_string) >= 2 and result_string[-1] == remaining_counts[i][0] and result_string[-2] == remaining_counts[i][0]:
                continue

            result_string += remaining_counts[i][0]
            remaining_counts[i][1] -= 1
            found = True
            break

        # If we can't add any character, we're done.
        if not found:
            break

    return result_string

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
a, b, and c are all zero	Return an empty string as no 'happy' string can be constructed.
One of a, b, or c is significantly larger than the sum of the other two (e.g., a = 100, b = 1, c = 1)	Prioritize the largest count, but ensure no three consecutive characters are the same to avoid violating 'happy' constraints.
a, b, and c are all equal	Construct the string by alternating the characters as much as possible to ensure all characters are included without exceeding length 2*count.
The sum of a, b, and c is very large potentially causing memory issues	The algorithm's space complexity scales linearly with the input counts so consider limiting the maximum allowed sum of a, b, and c.
Two of a, b, and c are zero	Return a string containing only the character associated with the non-zero count, limited to a length of the count itself.
All three counts are non-zero but very small (e.g., a=1, b=1, c=1)	Ensure correct handling of all permutations as all characters must be present in the output.
No valid solution exists because the counts are so skewed.	The algorithm handles this gracefully by prioritizing the highest count, and when no character can be appended without violating 'happy' constraints, it terminates and returns the best result generated.
Integer overflow when computing the length of the string	Ensure that you use a data type capable of holding values equal to the maximum possible sum of a, b, and c (e.g., int64_t in C++, long in Java, etc.)